제출 #1089039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089039		alexander707070	가로등 (APIO19_street_lamps)	C++14	100 / 100	1042 ms	378200 KiB

street_lamps

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20