oj.uz

Submission #973116

# Submission time Handle Problem Language Result Execution time Memory
973116 2024-05-01T13:51:39 Z simona1230 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 319088 KB 
#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];
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);
                }
            }
        }
        if(tp=="query")
        {
            cin>>x>>y;
            int add=0;
            if(itv.size())
            {
                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)<<'\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
*/

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 2512 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 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 231 ms 3352 KB Output is correct
2 Correct 383 ms 6120 KB Output is correct
3 Correct 746 ms 12468 KB Output is correct
4 Correct 2789 ms 224084 KB Output is correct
5 Correct 3244 ms 251300 KB Output is correct
6 Correct 3289 ms 237048 KB Output is correct
7 Correct 84 ms 6484 KB Output is correct
8 Correct 92 ms 7760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3164 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 3 ms 2904 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 4848 ms 319088 KB Output is correct
6 Correct 4337 ms 302476 KB Output is correct
7 Correct 3155 ms 248504 KB Output is correct
8 Correct 90 ms 7764 KB Output is correct
9 Correct 84 ms 4692 KB Output is correct
10 Correct 85 ms 5188 KB Output is correct
11 Correct 83 ms 5480 KB Output is correct
12 Correct 84 ms 6480 KB Output is correct
13 Correct 95 ms 7764 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 4 ms 2908 KB Output is correct
5 Correct 289 ms 22836 KB Output is correct
6 Correct 1656 ms 167012 KB Output is correct
7 Correct 3122 ms 235288 KB Output is correct
8 Execution timed out 5103 ms 277744 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 2512 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 231 ms 3352 KB Output is correct
9 Correct 383 ms 6120 KB Output is correct
10 Correct 746 ms 12468 KB Output is correct
11 Correct 2789 ms 224084 KB Output is correct
12 Correct 3244 ms 251300 KB Output is correct
13 Correct 3289 ms 237048 KB Output is correct
14 Correct 84 ms 6484 KB Output is correct
15 Correct 92 ms 7760 KB Output is correct
16 Correct 4 ms 3164 KB Output is correct
17 Correct 3 ms 2908 KB Output is correct
18 Correct 3 ms 2904 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 4848 ms 319088 KB Output is correct
21 Correct 4337 ms 302476 KB Output is correct
22 Correct 3155 ms 248504 KB Output is correct
23 Correct 90 ms 7764 KB Output is correct
24 Correct 84 ms 4692 KB Output is correct
25 Correct 85 ms 5188 KB Output is correct
26 Correct 83 ms 5480 KB Output is correct
27 Correct 84 ms 6480 KB Output is correct
28 Correct 95 ms 7764 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 2 ms 2652 KB Output is correct
31 Correct 3 ms 2908 KB Output is correct
32 Correct 4 ms 2908 KB Output is correct
33 Correct 289 ms 22836 KB Output is correct
34 Correct 1656 ms 167012 KB Output is correct
35 Correct 3122 ms 235288 KB Output is correct
36 Execution timed out 5103 ms 277744 KB Time limit exceeded
37 Halted 0 ms 0 KB -