oj.uz

Submission #973085

# Submission time Handle Problem Language Result Execution time Memory
973085 2024-05-01T13:34:07 Z simona1230 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 524288 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 3668 KB Output is correct
2 Correct 503 ms 3920 KB Output is correct
3 Correct 927 ms 13092 KB Output is correct
4 Correct 3385 ms 367144 KB Output is correct
5 Correct 3803 ms 420800 KB Output is correct
6 Correct 3784 ms 395584 KB Output is correct
7 Correct 412 ms 6520 KB Output is correct
8 Correct 421 ms 7904 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Runtime error 4694 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 3 ms 2904 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 4 ms 3164 KB Output is correct
5 Correct 644 ms 38304 KB Output is correct
6 Correct 2037 ms 297768 KB Output is correct
7 Correct 3390 ms 395416 KB Output is correct
8 Execution timed out 5077 ms 495452 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 409 ms 3668 KB Output is correct
9 Correct 503 ms 3920 KB Output is correct
10 Correct 927 ms 13092 KB Output is correct
11 Correct 3385 ms 367144 KB Output is correct
12 Correct 3803 ms 420800 KB Output is correct
13 Correct 3784 ms 395584 KB Output is correct
14 Correct 412 ms 6520 KB Output is correct
15 Correct 421 ms 7904 KB Output is correct
16 Correct 4 ms 3420 KB Output is correct
17 Correct 4 ms 3420 KB Output is correct
18 Correct 4 ms 3164 KB Output is correct
19 Correct 2 ms 2392 KB Output is correct
20 Runtime error 4694 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -