oj.uz

Submission #1089039

# Submission time Handle Problem Language Result Execution time Memory
1089039 2024-09-15T19:39:07 Z alexander707070 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1042 ms 378200 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#define MAXN 300007
using namespace std;

int n,q,x,l,r;
char c[MAXN];
int pref[MAXN];
string type;

struct intervals{
    int fenwick[MAXN];

    void update(int x,int val){
        while(x<=n){
            fenwick[x]+=val;
            x+=(x & (-x));
        }
    }

    int getsum(int x){
        int res=0;
        while(x>=1){
            res+=fenwick[x];
            x-=(x & (-x));
        }
        return res;
    }

    int sum(int l,int r){
        return getsum(r)-getsum(l-1);
    }

    int getlast(int l,int r){
        int tt,from=l,to=r;
        l--; r++;

        while(l+1<r){
            tt=(l+r)/2;
            if(sum(from,tt)==tt-from+1){
                l=tt;
            }else{
                r=tt;
            }
        }

        return l;
    }

    int getfirst(int l,int r){
        int tt,from=l,to=r;
        l--; r++;

        while(l+1<r){
            tt=(l+r)/2;
            if(sum(tt,to)==to-tt+1){
                r=tt;
            }else{
                l=tt;
            }
        }

        return r;
    }
}fen;

struct SegmentTree{
    struct node{
        int l,r;
        int val;
    };

    vector<node> tree;
    int num;

    void init(){
        tree.push_back({0,0,0});
        tree.push_back({0,0,0});
        num=1;
    }

    void addnode(){
        num++;
        tree.push_back({0,0,0});
    }

    void update(int v,int l,int r,int ll,int rr,int val){
        if(ll>rr)return;
        if(l==ll and r==rr){
            tree[v].val+=val;
        }else{
            int tt=(l+r)/2;

            if(tree[v].l==0){
                addnode(); tree[v].l=num;
            }

            if(tree[v].r==0){
                addnode(); tree[v].r=num;
            }

            update(tree[v].l,l,tt,ll,min(tt,rr),val);
            update(tree[v].r,tt+1,r,max(tt+1,ll),rr,val);
        }
    }

    int getval(int v,int l,int r,int pos){
        if(v==0)return 0;
        if(l==r)return tree[v].val;

        int tt=(l+r)/2;
        if(pos<=tt)return getval(tree[v].l,l,tt,pos)+tree[v].val;
        else return getval(tree[v].r,tt+1,r,pos)+tree[v].val;
    }

    void upd(int l,int r,int val){
        update(1,1,n,l,r,val);
    }

    int query(int pos){
        return getval(1,1,n,pos);
    }
};

struct SegmentTree2D{
    struct node{
        SegmentTree t;
        int l,r;
    };

    node tree[4*MAXN];

    void init(){
        for(int i=1;i<4*MAXN;i++){
            tree[i].t.init();
        }
    }

    void update(int v,int l,int r,int lx,int rx,int ly,int ry,int val){
        if(lx>rx)return;
        if(l==lx and r==rx){
            tree[v].t.upd(ly,ry,val);
        }else{
            int tt=(l+r)/2;
            update(2*v,l,tt,lx,min(rx,tt),ly,ry,val);
            update(2*v+1,tt+1,r,max(lx,tt+1),rx,ly,ry,val);
        }
    }

    int getval(int v,int l,int r,int x,int y){
        if(l==r){
            return tree[v].t.query(y);
        }else{
            int tt=(l+r)/2;
            if(x<=tt)return getval(2*v,l,tt,x,y) + tree[v].t.query(y);
            else return getval(2*v+1,tt+1,r,x,y) + tree[v].t.query(y);
        }
    }

    void upd(int lx,int rx,int ly,int ry,int val){
        update(1,1,n,lx,rx,ly,ry,val);
    }

    int query(int x,int y){
        return getval(1,1,n,x,y);
    }
}tree;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q>>(c+1);
    tree.init();

    for(int i=1;i<=n;i++){
        pref[i]=(c[i]-'0')+pref[i-1];

        if(c[i]=='1')fen.update(i,1);
    }

    for(int i=1;i<=q;i++){
        cin>>type;
        if(type=="toggle"){
            cin>>x;
            if(c[x]=='1'){
                c[x]='0';
                int a=fen.getfirst(1,x);
                int b=fen.getlast(x,n);
                fen.update(x,-1);

                tree.upd(a,x,x,b,i);
            }else{
                c[x]='1';
                fen.update(x,1);
                int a=fen.getfirst(1,x);
                int b=fen.getlast(x,n);

                tree.upd(a,x,x,b,-i);
            }
        }else{
            cin>>l>>r; r--;

            int curr=0;
            int a=fen.getlast(l,r);
            if(a==r)curr+=i;

            cout<<tree.query(l,r)+curr<<"\n";
        }
    }

    return 0;
}

Compilation message

street_lamps.cpp: In member function 'int intervals::getlast(int, int)':
street_lamps.cpp:37:23: warning: unused variable 'to' [-Wunused-variable]
   37 |         int tt,from=l,to=r;
      |                       ^~
street_lamps.cpp: In member function 'int intervals::getfirst(int, int)':
street_lamps.cpp:53:16: warning: unused variable 'from' [-Wunused-variable]
   53 |         int tt,from=l,to=r;
      |                ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 84820 KB Output is correct
2 Correct 89 ms 84800 KB Output is correct
3 Correct 97 ms 84816 KB Output is correct
4 Correct 113 ms 84816 KB Output is correct
5 Correct 91 ms 84816 KB Output is correct
6 Correct 112 ms 84820 KB Output is correct
7 Correct 87 ms 84992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 89172 KB Output is correct
2 Correct 246 ms 89684 KB Output is correct
3 Correct 317 ms 96080 KB Output is correct
4 Correct 698 ms 208516 KB Output is correct
5 Correct 711 ms 265040 KB Output is correct
6 Correct 625 ms 223572 KB Output is correct
7 Correct 270 ms 92768 KB Output is correct
8 Correct 294 ms 95412 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 85332 KB Output is correct
2 Correct 102 ms 85332 KB Output is correct
3 Correct 93 ms 85288 KB Output is correct
4 Correct 93 ms 84820 KB Output is correct
5 Correct 1042 ms 378200 KB Output is correct
6 Correct 895 ms 328244 KB Output is correct
7 Correct 760 ms 264020 KB Output is correct
8 Correct 388 ms 95548 KB Output is correct
9 Correct 162 ms 88540 KB Output is correct
10 Correct 175 ms 88912 KB Output is correct
11 Correct 186 ms 89044 KB Output is correct
12 Correct 375 ms 92752 KB Output is correct
13 Correct 378 ms 95532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 84844 KB Output is correct
2 Correct 98 ms 85076 KB Output is correct
3 Correct 97 ms 85076 KB Output is correct
4 Correct 116 ms 85328 KB Output is correct
5 Correct 388 ms 97320 KB Output is correct
6 Correct 547 ms 171420 KB Output is correct
7 Correct 704 ms 223312 KB Output is correct
8 Correct 848 ms 273044 KB Output is correct
9 Correct 243 ms 88916 KB Output is correct
10 Correct 191 ms 87828 KB Output is correct
11 Correct 240 ms 88900 KB Output is correct
12 Correct 200 ms 88052 KB Output is correct
13 Correct 231 ms 89008 KB Output is correct
14 Correct 191 ms 87952 KB Output is correct
15 Correct 387 ms 92916 KB Output is correct
16 Correct 398 ms 95348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 84820 KB Output is correct
2 Correct 89 ms 84800 KB Output is correct
3 Correct 97 ms 84816 KB Output is correct
4 Correct 113 ms 84816 KB Output is correct
5 Correct 91 ms 84816 KB Output is correct
6 Correct 112 ms 84820 KB Output is correct
7 Correct 87 ms 84992 KB Output is correct
8 Correct 195 ms 89172 KB Output is correct
9 Correct 246 ms 89684 KB Output is correct
10 Correct 317 ms 96080 KB Output is correct
11 Correct 698 ms 208516 KB Output is correct
12 Correct 711 ms 265040 KB Output is correct
13 Correct 625 ms 223572 KB Output is correct
14 Correct 270 ms 92768 KB Output is correct
15 Correct 294 ms 95412 KB Output is correct
16 Correct 94 ms 85332 KB Output is correct
17 Correct 102 ms 85332 KB Output is correct
18 Correct 93 ms 85288 KB Output is correct
19 Correct 93 ms 84820 KB Output is correct
20 Correct 1042 ms 378200 KB Output is correct
21 Correct 895 ms 328244 KB Output is correct
22 Correct 760 ms 264020 KB Output is correct
23 Correct 388 ms 95548 KB Output is correct
24 Correct 162 ms 88540 KB Output is correct
25 Correct 175 ms 88912 KB Output is correct
26 Correct 186 ms 89044 KB Output is correct
27 Correct 375 ms 92752 KB Output is correct
28 Correct 378 ms 95532 KB Output is correct
29 Correct 87 ms 84844 KB Output is correct
30 Correct 98 ms 85076 KB Output is correct
31 Correct 97 ms 85076 KB Output is correct
32 Correct 116 ms 85328 KB Output is correct
33 Correct 388 ms 97320 KB Output is correct
34 Correct 547 ms 171420 KB Output is correct
35 Correct 704 ms 223312 KB Output is correct
36 Correct 848 ms 273044 KB Output is correct
37 Correct 243 ms 88916 KB Output is correct
38 Correct 191 ms 87828 KB Output is correct
39 Correct 240 ms 88900 KB Output is correct
40 Correct 200 ms 88052 KB Output is correct
41 Correct 231 ms 89008 KB Output is correct
42 Correct 191 ms 87952 KB Output is correct
43 Correct 387 ms 92916 KB Output is correct
44 Correct 398 ms 95348 KB Output is correct
45 Correct 129 ms 87400 KB Output is correct
46 Correct 170 ms 87580 KB Output is correct
47 Correct 427 ms 148636 KB Output is correct
48 Correct 646 ms 207952 KB Output is correct
49 Correct 161 ms 89168 KB Output is correct
50 Correct 167 ms 89180 KB Output is correct
51 Correct 169 ms 89244 KB Output is correct
52 Correct 172 ms 89428 KB Output is correct
53 Correct 181 ms 89428 KB Output is correct
54 Correct 165 ms 89428 KB Output is correct