oj.uz

Submission #1087071

# Submission time Handle Problem Language Result Execution time Memory
1087071 2024-09-12T07:26:50 Z alexander707070 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 57 ms 20512 KB 
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

struct ST{
    int tree[4*MAXN],tree2[4*MAXN];

    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v]=tree2[v]=val;
        }else{
            int tt=(l+r)/2;
            if(pos<=tt)update(2*v,l,tt,pos,val);
            else update(2*v+1,tt+1,r,pos,val);

            tree[v]=min(tree[2*v],tree[2*v+1]);
            tree2[v]=max(tree2[2*v],tree2[2*v+1]);
        }
    }

    int getmin(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 1;
        if(l==ll and r==rr){
            return tree[v];
        }else{
            int tt=(l+r)/2;
            return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }

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

int n,q,tim,x,l,r;
char c[MAXN];
int last[MAXN],sum[MAXN];
string type;

int d[107][107];

int main(){

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

    cin>>n>>q>>(c+1);
    for(int i=1;i<=n;i++){
        if(c[i]=='1')st.update(1,1,n,i,1);

        d[0][i]=c[i];
    }

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

            if(q<=100){
                int res=0;
                for(int f=0;f<i;f++){
                    for(int k=l;k<r;k++){
                        if(d[f][k]=='0')break;
                        else if(k==r-1)res++;
                    }
                }
                cout<<res<<"\n";
            }else if(l+1<r){
                int s=st.getmin(1,1,n,l,r-1);
                if(s==0)cout<<0<<"\n";
                else cout<<i+1-st.getmax(1,1,n,l,r-1)<<"\n";
            }else{
                if(c[l]=='0')cout<<sum[l]<<"\n";
                else cout<<sum[l]+i-last[l]<<"\n";
            }
        }

        if(n<=100 and q<=100){
            for(int f=1;f<=n;f++)d[i][f]=c[f];
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4564 KB Output is correct
2 Correct 57 ms 4952 KB Output is correct
3 Correct 54 ms 5244 KB Output is correct
4 Runtime error 24 ms 20512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 13 ms 18780 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 47 ms 4564 KB Output is correct
9 Correct 57 ms 4952 KB Output is correct
10 Correct 54 ms 5244 KB Output is correct
11 Runtime error 24 ms 20512 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -