珂朵莉树70pts WA求调
  • 板块P2070 刷墙
  • 楼主Jasmine_Aura
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/15 21:03
  • 上次更新2023/11/15 22:18:59
查看原帖
珂朵莉树70pts WA求调
717578
Jasmine_Aura楼主2023/11/15 21:03

rt

#include<bits/stdc++.h>
using namespace std;
#define IT set<odt>::iterator 
#define int long long
template<typename T>
void read(T &x)
{
    x=0;
    int f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+(ch^48);
        ch=getchar();
    }
    x*=f;
}
struct odt
{
    int l,r;
    mutable int val;
    bool operator <(const odt &x)const
    {
        return l<x.l;
    }
};
set<odt>ODT;
IT split(int pos)
{
    IT it=ODT.lower_bound({pos,-10000000000,0});
    if(it!=ODT.end()&&it->l==pos)return it;
    it--;
    int l=it->l;
    int r=it->r;
    int val=it->val;
    ODT.erase(it);
    ODT.insert({l,pos-1,val});
    return ODT.insert({pos,r,val}).first;
}
void modify(int l,int r,int add)
{
    IT itr=split(r+1);
    IT itl=split(l);
    for(;itl!=itr;itl++)itl->val+=add;
}
int query(int l,int r)
{
    IT itr=split(r+1);
    IT itl=split(l);
    int ans=0;
    for(;itl!=itr;itl++)if(itl->val>=2)ans+=(itl->r-itl->l+1);
    return ans;
}
signed main()
{
    int l=-1000000005,r=1000000005;
    ODT.insert({l,r,0});
    int n,x,pos=0;
    char opt;
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(x);
        cin>>opt;
        if(opt=='R')
        {
            modify(pos+1,pos+x,1);
            pos=pos+x;
        }
        else
        {
            modify(pos-x,pos-1,1);
            pos=pos-x;
        }
    }
    cout<<query(l,r)<<endl;
    return 0;
}
2023/11/15 21:03
加载中...