Submission #1208805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208805		avohado	Street Lamps (APIO19_street_lamps)	C++20	40 / 100	165 ms	10944 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 300005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, m;
string s;
int mtree[maxn*4], xtree[maxn*4], a[maxn];
void bt(int v, int tl, int tr){
    if(tl==tr){
        if(s[tl]=='1'){
            mtree[v]=INT_MAX;
            xtree[v]=0;
        }else{
            mtree[v]=0;
            xtree[v]=-1;
        }
        return;
    }
    int tm=(tr+ tl)/2;
    bt(v*2, tl, tm);
    bt(v*2+1, tm+1, tr);
    mtree[v]=min(mtree[v*2], mtree[v*2+1]);
    xtree[v]=max(xtree[v*2], xtree[v*2+1]);
}
void upd(int v, int l, int tl, int tr, int j){
    if(tl==tr){
        if(s[tl]=='1'){
            s[tl]='0';
            mtree[v]=j-xtree[v]+1;
            xtree[v]=-1;
        }else{
            s[tl]='1';
            xtree[v]=j-mtree[v]+1;
            mtree[v]=INT_MAX;
        }
        return;
    }
    int tm=(tl+tr)/2;
    if(tm<l){
        upd(v*2+1, l, tm+1, tr, j);
    }else{
        upd(v*2, l, tl, tm, j);
    }
    mtree[v]=min(mtree[v*2], mtree[v*2+1]);
    xtree[v]=max(xtree[v*2], xtree[v*2+1]);
}
pair<int,int> res(int v, int l, int r, int tl, int tr){
    if(tl>r||l>tr){
        return {INT_MAX, -1};
    }
    if(l<=tl&&tr<=r){
        return {mtree[v], xtree[v]};
    }
    pair<int, int> a=res(v*2, l, r, tl, (tl+tr)/2), b=res(v*2+1, l, r,(tl+tr)/2+1, tr);
    return {min(a.f,b.f), max(a.s, b.s)};
}
void solve(){
    cin >> n >> m;
    cin >> s;
    string s1;
    bt(1, 0, n-1);
    for(int i=0; i<m; i++){
        cin >> s1;
        if(s1[0]=='q'){
            int l, r;
            cin >> l >> r;
            l--; r-=2;
            pair<int, int> a=res(1, l, r, 0, n-1);
            cout << min(a.f, i+1-a.s);
            cout << "\n";
        }else{
            int x;
            cin >> x;
            upd(1, x-1, 0, n-1, i);
        }
    }
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

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