Submission #1087071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087071		alexander707070	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	57 ms	20512 KiB

street_lamps

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