oj.uz

Submission #1087120

# Submission time Handle Problem Language Result Execution time Memory
1087120 2024-09-12T08:31:04 Z alexander707070 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 53664 KB 
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

const int bucket_sz=500;

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26204 KB Output is correct
2 Correct 11 ms 26100 KB Output is correct
3 Correct 11 ms 26204 KB Output is correct
4 Correct 12 ms 26200 KB Output is correct
5 Correct 11 ms 26204 KB Output is correct
6 Correct 11 ms 26208 KB Output is correct
7 Correct 10 ms 26204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 38240 KB Output is correct
2 Correct 178 ms 38736 KB Output is correct
3 Correct 191 ms 39344 KB Output is correct
4 Correct 232 ms 48140 KB Output is correct
5 Correct 234 ms 51960 KB Output is correct
6 Correct 227 ms 47296 KB Output is correct
7 Correct 188 ms 38952 KB Output is correct
8 Correct 206 ms 53664 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26204 KB Output is correct
2 Correct 15 ms 26332 KB Output is correct
3 Correct 13 ms 26204 KB Output is correct
4 Correct 13 ms 26320 KB Output is correct
5 Execution timed out 5017 ms 47344 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26200 KB Output is correct
2 Correct 17 ms 26372 KB Output is correct
3 Correct 15 ms 26204 KB Output is correct
4 Correct 14 ms 26388 KB Output is correct
5 Correct 2729 ms 48864 KB Output is correct
6 Execution timed out 5024 ms 47636 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26204 KB Output is correct
2 Correct 11 ms 26100 KB Output is correct
3 Correct 11 ms 26204 KB Output is correct
4 Correct 12 ms 26200 KB Output is correct
5 Correct 11 ms 26204 KB Output is correct
6 Correct 11 ms 26208 KB Output is correct
7 Correct 10 ms 26204 KB Output is correct
8 Correct 180 ms 38240 KB Output is correct
9 Correct 178 ms 38736 KB Output is correct
10 Correct 191 ms 39344 KB Output is correct
11 Correct 232 ms 48140 KB Output is correct
12 Correct 234 ms 51960 KB Output is correct
13 Correct 227 ms 47296 KB Output is correct
14 Correct 188 ms 38952 KB Output is correct
15 Correct 206 ms 53664 KB Output is correct
16 Correct 13 ms 26204 KB Output is correct
17 Correct 15 ms 26332 KB Output is correct
18 Correct 13 ms 26204 KB Output is correct
19 Correct 13 ms 26320 KB Output is correct
20 Execution timed out 5017 ms 47344 KB Time limit exceeded
21 Halted 0 ms 0 KB -