Submission #934199

#	Time	Username	Problem	Language	Result	Execution time	Memory
934199		irmuun	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	81 ms	19592 KiB

street_lamps

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    vector<ll>u;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=max(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,q;
    cin>>n>>q;
    char s[n+5],cur[n+5];
    for(ll i=1;i<=n;i++){
        cin>>s[i];
    }
    bool sub2=true;
    vector<pair<ll,ll>>que(q+1);
    for(ll i=1;i<=q;i++){
        string t;
        cin>>t;
        if(t=="toggle"){
            ll j;
            cin>>j;
            que[i]={j,-1};
        }
        else{
            ll a,b;
            cin>>a>>b;
            que[i]={a,b};
            sub2|=(a+1==b);
        }
    }
    if(n<=100&&q<=100){
        for(ll i=1;i<=q;i++){
            if(que[i].ss==-1) continue;
            ll ans=0;
            for(ll j=1;j<=n;j++){
                cur[j]=s[j];
            }
            ll a=que[i].ff,b=que[i].ss;
            for(ll j=1;j<=i;j++){
                bool ok=true;
                for(ll k=a;k<b;k++){
                    if(cur[k]=='0'){
                        ok=false;
                        break;
                    }
                }
                if(ok){
                    ans++;
                }
                if(que[j].ss==-1){
                    ll p=que[j].ff;
                    if(cur[p]=='1') cur[p]='0';
                    else cur[p]='1';
                }
            }
            cout<<ans<<"\n";
        }
        return 0;
    }
    if(sub2){
        vector<pair<ll,ll>>bef(n+1);
        for(ll i=1;i<=n;i++){
            bef[i].ff=0;
            bef[i].ss=s[i]-'0';
        }
        vector<ll>ans(n+1,0);
        for(ll i=1;i<=q;i++){
            if(que[i].ss==-1){
                ll j=que[i].ff;
                if(bef[j].ss==1){
                    ans[j]+=i-bef[j].ff;
                }
                bef[j].ff=i;
                bef[j].ss=1-bef[j].ss;
            }
            else{
                ll a,b;
                a=que[i].ff;
                b=que[i].ss;
                if(a==b-1){
                    if(bef[a].ss==1){
                        ans[a]+=i-bef[a].ff;
                    }
                    bef[a].ff=i;
                    cout<<ans[a]<<"\n";
                }
            }
        }
        return 0;
    }
    segtree sg(n);
    for(ll i=1;i<=n;i++){
        if(s[i]=='1'){
            sg.update(1,1,n,i,0);
        }
        else{
            sg.update(1,1,n,i,1e18);
        }
    }
    for(ll i=1;i<=q;i++){
        if(que[i].ss==-1){
            ll j=que[i].ff;
            sg.update(1,1,n,j,i);
        }
        else{
            ll a=que[i].ff,b=que[i].ss;
            ll x=sg.query(1,1,n,a,b-1);
            cout<<max(i-x,0ll)<<"\n";
        }
    }
}

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