oj.uz

Submission #1087125

# Submission time Handle Problem Language Result Execution time Memory
1087125 2024-09-12T08:35:11 Z alexander707070 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 51396 KB 
#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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 38224 KB Output is correct
2 Correct 178 ms 38484 KB Output is correct
3 Correct 190 ms 39000 KB Output is correct
4 Correct 242 ms 47400 KB Output is correct
5 Correct 211 ms 50260 KB Output is correct
6 Correct 235 ms 45136 KB Output is correct
7 Correct 165 ms 36652 KB Output is correct
8 Correct 189 ms 51396 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26204 KB Output is correct
2 Correct 13 ms 26168 KB Output is correct
3 Correct 13 ms 26200 KB Output is correct
4 Correct 15 ms 26712 KB Output is correct
5 Execution timed out 5054 ms 46120 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26200 KB Output is correct
2 Correct 14 ms 26204 KB Output is correct
3 Correct 14 ms 26204 KB Output is correct
4 Correct 11 ms 26376 KB Output is correct
5 Correct 1853 ms 46296 KB Output is correct
6 Execution timed out 5017 ms 46896 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26204 KB Output is correct
2 Correct 10 ms 26240 KB Output is correct
3 Correct 10 ms 26200 KB Output is correct
4 Correct 11 ms 26204 KB Output is correct
5 Correct 11 ms 26312 KB Output is correct
6 Correct 11 ms 26100 KB Output is correct
7 Correct 11 ms 26204 KB Output is correct
8 Correct 154 ms 38224 KB Output is correct
9 Correct 178 ms 38484 KB Output is correct
10 Correct 190 ms 39000 KB Output is correct
11 Correct 242 ms 47400 KB Output is correct
12 Correct 211 ms 50260 KB Output is correct
13 Correct 235 ms 45136 KB Output is correct
14 Correct 165 ms 36652 KB Output is correct
15 Correct 189 ms 51396 KB Output is correct
16 Correct 12 ms 26204 KB Output is correct
17 Correct 13 ms 26168 KB Output is correct
18 Correct 13 ms 26200 KB Output is correct
19 Correct 15 ms 26712 KB Output is correct
20 Execution timed out 5054 ms 46120 KB Time limit exceeded
21 Halted 0 ms 0 KB -