Submission #1087125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087125		alexander707070	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	5054 ms	51396 KiB

street_lamps

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 300007
using namespace std;

const int bucket_sz=1000;

int n,q,tim,x,l,r,pt;
char c[MAXN];
int last[MAXN],bucket[MAXN],ans[MAXN];
string type[MAXN];
vector< pair<int,int> > events[MAXN];

struct ST{
    int lazy[4*MAXN];
    pair<int,int> tree[4*MAXN];

    void build(int v,int l,int r){
        if(l==r){
            tree[v]={0,1};
        }else{
            int tt=(l+r)/2;
            build(2*v,l,tt);
            build(2*v+1,tt+1,r);

            tree[v]={0,r-l+1};
        }
    }

    pair<int,int> combine(pair<int,int> fr, pair<int,int> sc){
        if(fr.first>sc.first)return fr;
        if(sc.first>fr.first)return sc;
        return {fr.first,fr.second+sc.second};
    }

    void psh(int v){
        if(lazy[v]==0)return;

        tree[2*v].first+=lazy[v];
        lazy[2*v]+=lazy[v];

        tree[2*v+1].first+=lazy[v];
        lazy[2*v+1]+=lazy[v];

        lazy[v]=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].first+=val;
            lazy[v]+=val;
        }else{
            psh(v);
            int tt=(l+r)/2;

            update(2*v,l,tt,ll,min(tt,rr),val);
            update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

            tree[v]=combine(tree[2*v],tree[2*v+1]);
        }
    }

    pair<int,int> getmax(int v,int l,int r,int ll,int rr){
        if(ll>rr)return {0,0};
        if(l==ll and r==rr){
            return tree[v];
        }else{
            psh(v);
            int tt=(l+r)/2;
            return combine( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }
}st;

struct query{
    int l,r,t;

    inline friend bool operator < (query fr,query sc){
        if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l];
        return fr.r<sc.r;
    }
}qs[MAXN];

void add(int id){
    for(pair<int,int> curr:events[id]){
        st.update(1,0,q,curr.first,curr.second,1);
    }
}

void rem(int id){
    for(pair<int,int> curr:events[id]){
        st.update(1,0,q,curr.first,curr.second,-1);
    }
}

int ask(int sz,int t){
    pair<int,int> info=st.getmax(1,0,q,0,t);
    if(info.first<sz)return 0;
    return info.second;
}

int main(){

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

    cin>>n>>q>>(c+1);

    for(int i=1;i<=q;i++){
        cin>>type[i];
        if(type[i]=="toggle"){
            cin>>x;
            if(c[x]=='0'){
                c[x]='1'; last[x]=i;
            }else{
                events[x].push_back({last[x],i-1});
                c[x]='0';
            }
        }else{
            cin>>l>>r; r--; pt++;
            qs[pt]={l,r,i-1};
        }
    }

    for(int i=1;i<=n;i++){
        if(c[i]=='1')events[i].push_back({last[i],q});
    }

    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=int(events[i].size())+1;
        bucket[i]=sum/bucket_sz;
    }

    sort(qs+1,qs+pt+1);
    st.build(1,0,q);

    l=1; r=0;
    for(int i=1;i<=pt;i++){
        while(r<qs[i].r){
            r++; add(r);
        }

        while(l>qs[i].l){
            l--; add(l);
        }

        while(r>qs[i].r){
            rem(r); r--;
        }

        while(l<qs[i].l){
            rem(l); l++;
        }

        ans[qs[i].t]=ask(qs[i].r-qs[i].l+1,qs[i].t);
    }

    for(int i=1;i<=q;i++){
        if(type[i]=="query")cout<<ans[i-1]<<"\n";
    }

    return 0;
}

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