Submission #973467

#	Time	Username	Problem	Language	Result	Execution time	Memory
973467		simona1230	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4964 ms	324132 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
const int maxn=3*1e5+5;
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;
        }

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

        if(lf==-1)v[i].val=v[rt].val;
        else if(rt==-1)v[i].val=v[lf].val;
        else 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;
        }

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

        int val1=0;
        int val2=0;

        if(lf!=-1)
            val1=v[lf].s.query(0,1,n,other,other);

        if(rt!=-1)
            val2=v[rt].s.query(0,1,n,other,other);

        int curr=val1+val2;
        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];
int t[4*maxn];

void update(int i,int l,int r,int idx,int val)
{
    if(l==r)
    {
        if(val==0)t[i]=l;
        else t[i]=n+1;
        return;
    }

    int m=(l+r)/2;
    if(idx<=m)update(i*2,l,m,idx,val);
    else update(i*2+1,m+1,r,idx,val);

    t[i]=min(t[i*2],t[i*2+1]);
}

int previous(int i,int l,int r,int idx)
{
    //cout<<l<<" "<<r<<" "<<t[i]<<endl;
    //cout<<l<<" "<<r<<" "<<t[i]<<endl;
    if(l==r)return l;
    int m=(l+r)/2;
    //cout<<"+ "<<m<<" "<<t[i*2+1]<<endl;
    if(t[i*2+1]<idx)return previous(i*2+1,m+1,r,idx);
    else return previous(i*2,l,m,idx);
}

void read()
{
    cin>>n>>q;
    for(int i=1;i<=4*n;i++)
        t[i]=n+1;

    int bg=-1;
    for(int i=1; i<=n; i++)
    {
        cin>>c[i];
        if(c[i]=='0')
        {
            update(1,0,n+1,i,0);
            if(bg!=-1)
            {
                r[bg]=i-1;
                tmr[bg]=0;
            }
            bg=-1;
        }
        else
        {
            update(1,0,n+1,i,1);
            if(bg==-1)bg=i;
        }
    }
    if(bg!=-1)
    {
        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;
            int prv=previous(1,0,n+1,x)+1;
            //cout<<prv<<endl;
            //cout<<prv<<endl;
            if(c[x]=='0')
            {
                c[x]='1';
                update(1,0,n+1,x,1);
                if(c[x-1]=='0'&&c[x+1]=='0')
                {
                    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;
                }
                else if(c[x+1]=='0')
                {
                    int lf=prv;
                    s.update(0,1,n,lf,i-tmr[lf],x-1);
                    r[lf]=x;
                    tmr[lf]=i;
                }
                else
                {
                    //cout<<"in"<<endl;
                    int lf=prv;
                    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;
                }
            }
            else
            {
                c[x]='0';
                update(1,0,n+1,x,0);
                s.update(0,1,n,prv,i-tmr[prv],r[prv]);
                if(c[x-1]=='0'&&c[x+1]=='0')
                {
                    ;
                }
                else if(c[x-1]=='0')
                {
                    tmr[x+1]=i;
                    r[x+1]=r[x];
                }
                else if(c[x+1]=='0')
                {
                    tmr[prv]=i;
                    r[prv]=x-1;
                }
                else
                {
                    tmr[prv]=tmr[x+1]=i;
                    r[x+1]=r[prv];
                    r[prv]=x-1;
                    itv.insert(x+1);
                }
            }
        }
        if(tp=="query")
        {
            cin>>x>>y;
            int add=0;
            int prv=previous(1,0,n+1,x)+1;
            if(c[x]=='1'&&prv<=x&&r[prv]>=y-1)add=i-tmr[prv];
            //cout<<prv<<" "<<r[prv]<<endl;
            cout<<add+s.query(0,1,n,1,x,y-1,n)<<'\n';
        }
    }
}

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

1
2
3
1
8
9
*/

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