Submission #934206

#	Time	Username	Problem	Language	Result	Execution time	Memory
934206		irmuun	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	199 ms	22608 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];
    }
    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};
        }
    }
    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";
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:57:17: warning: unused variable 'cur' [-Wunused-variable]
   57 |     char s[n+5],cur[n+5];
      |                 ^~~

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