Submission #973085

#	Time	Username	Problem	Language	Result	Execution time	Memory
973085		simona1230	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5077 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
const int maxn=4*1e5;
int n,q;
struct node
{
    int l,r;
    int val;
    node() {}
    node(int _l,int _r,int v)
    {
        l=_l;
        r=_r;
        val=v;
    }
};

struct segmentTree
{
    vector<node> v= {{-1,-1,0}};

    void makeLeft(int i)
    {
        v[i].l=v.size();
        v.push_back({-1,-1,0});
    }

    void makeRight(int i)
    {
        v[i].r=v.size();
        v.push_back({-1,-1,0});
    }

    int query(int i,int l,int r,int ql,int qr)
    {
        if(ql>qr||i==-1)return 0;
        if(ql<=l&&r<=qr)return v[i].val;

        int m=(l+r)/2;
        return query(v[i].l,l,m,ql,min(qr,m))+query(v[i].r,m+1,r,max(ql,m+1),qr);
    }

    void update(int i,int l,int r,int idx,int val)
    {
        //cout<<l<<" nml "<<r<<endl;
        if(l==r)
        {
            if(val>0)v[i].val+=val;
            else v[i].val=-val;
            return;
        }

        if(v[i].l==-1)makeLeft(i);
        if(v[i].r==-1)makeRight(i);

        int lf=v[i].l,rt=v[i].r;
        int m=(l+r)/2;
        if(idx<=m)update(lf,l,m,idx,val);
        else update(rt,m+1,r,idx,val);

        v[i].val=v[lf].val+v[rt].val;
    }
};

struct twoDnode
{
    segmentTree s;
    int l,r;
    twoDnode() {}
    twoDnode(segmentTree _s,int _l,int _r)
    {
        s=_s;
        l=_l;
        r=_r;
    }
};

struct twoD
{
    segmentTree g;
    vector<twoDnode> v= {{g,-1,-1}};


    void makeLeft(int i)
    {
        v[i].l=v.size();
        v.push_back({g,-1,-1});
    }

    void makeRight(int i)
    {
        v[i].r=v.size();
        v.push_back({g,-1,-1});
    }

    void update(int i,int l,int r,int idx,int val,int other)
    {
        //cout<<l<<" 2d "<<r<<endl;
        if(l==r)
        {
            v[i].s.update(0,1,n,other,val);
            return;
        }

        if(v[i].l==-1)makeLeft(i);
        if(v[i].r==-1)makeRight(i);

        int lf=v[i].l,rt=v[i].r;
        //cout<<lf<<" "<<rt<<endl;
        int m=(l+r)/2;
        if(idx<=m)update(lf,l,m,idx,val,other);
        else update(rt,m+1,r,idx,val,other);

        int curr=v[lf].s.query(0,1,n,other,other)+v[rt].s.query(0,1,n,other,other);
        v[i].s.update(0,1,n,other,-curr);
    }

    int query(int i,int l,int r,int ql,int qr,int h1,int h2)
    {
        if(ql>qr||i==-1)return 0;
        if(ql<=l&&r<=qr)return v[i].s.query(0,1,n,h1,h2);

        int lf=v[i].l,rt=v[i].r;
        int m=(l+r)/2;
        return query(lf,l,m,ql,min(qr,m),h1,h2)+query(rt,m+1,r,max(m+1,ql),qr,h1,h2);
    }
};

twoD s;
set<int> itv;
int l[maxn],r[maxn],tmr[maxn];
char c[maxn];
void read()
{
    cin>>n>>q;

    int bg=-1;
    for(int i=1; i<=n; i++)
    {
        cin>>c[i];
        if(c[i]=='0')
        {
            if(bg!=-1)
            {
                itv.insert(bg);
                r[bg]=i-1;
                tmr[bg]=0;
            }
            bg=-1;
        }
        else
        {
            if(bg==-1)bg=i;
        }
    }
    if(bg!=-1)
    {
        itv.insert(bg);
        r[bg]=n;
        tmr[bg]=0;
    }
}

void solve()
{
    c[0]=c[n+1]='0';
    for(int i=1; i<=q; i++)
    {
        string tp;
        int x,y;
        cin>>tp;
        if(tp=="toggle")
        {
            cin>>x;
            if(c[x]=='0')
            {
                c[x]='1';
                if(c[x-1]=='0'&&c[x+1]=='0')
                {
                    itv.insert(x);
                    r[x]=x;
                    tmr[x]=i;
                }
                else if(c[x-1]=='0')
                {
                    s.update(0,1,n,x+1,i-tmr[x+1],r[x+1]);
                    r[x]=r[x+1];
                    tmr[x]=i;
                    itv.erase(x+1);
                    itv.insert(x);
                }
                else if(c[x+1]=='0')
                {
                    auto it=itv.upper_bound(x);
                    it--;
                    int lf=*it;
                    s.update(0,1,n,lf,i-tmr[lf],x-1);
                    r[lf]=x;
                    tmr[lf]=i;
                }
                else
                {
                    //cout<<"in"<<endl;
                    auto it=itv.upper_bound(x);
                    it--;
                    int lf=*it;
                    s.update(0,1,n,lf,i-tmr[lf],x-1);
                    s.update(0,1,n,x+1,i-tmr[x+1],r[x+1]);
                    r[lf]=r[x+1];
                    tmr[lf]=i;
                    //cout<<lf<<" "<<r[x+1]<<endl;
                    itv.erase(x+1);
                }
            }
            else
            {
                c[x]='0';
                auto it=itv.upper_bound(x);
                it--;
                s.update(0,1,n,*it,i-tmr[*it],r[*it]);
                if(c[x-1]=='0'&&c[x+1]=='0')
                {
                    itv.erase(x);
                }
                else if(c[x-1]=='0')
                {
                    itv.erase(x);
                    itv.insert(x+1);
                    tmr[x+1]=i;
                    r[x+1]=r[x];
                }
                else if(c[x+1]=='0')
                {
                    tmr[*it]=i;
                    r[*it]=x-1;
                }
                else
                {
                    tmr[*it]=tmr[x+1]=i;
                    r[x+1]=r[*it];
                    r[*it]=x-1;
                    itv.insert(x+1);
                }
            }
            /*for(auto it=itv.begin();it!=itv.end();it++)
            {
                cout<<*it<<" "<<r[*it]<<" "<<tmr[*it]<<endl;
            }*/
        }
        if(tp=="query")
        {
            cin>>x>>y;
            int add=0;
            if(itv.size())
            {
                auto ch=itv.rbegin();
                if(*ch<=x)
                {
                    if(r[*ch]>=y-1)
                        add=i-tmr[*ch];
                }
                else
                {
                    auto it=itv.upper_bound(x);
                    it--;
                    if(*itv.begin()<=x&&r[*it]>=y-1)
                        add=i-tmr[*it];
                }
            }
            cout<<add+s.query(0,1,n,1,x,y-1,n)<<endl;
        }
        /*for(int j=1;j<=n;j++)
            cout<<c[j];
        cout<<endl;*/
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    solve();
    return 0;
}
/*
7 10
0110101
query 2 3
toggle 2
query 2 3
toggle 2
query 2 3
toggle 6
query 5 7
query 6 6
toggle 5
query 5 5
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20