Submission #985225

#	Time	Username	Problem	Language	Result	Execution time	Memory
985225		nnin	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	214 ms	13084 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;

int n, q;

int seg[1200005];
void build(int i, int l, int r) {
    seg[i] = 1e9;
    if(l==r) return;
    int m = (l+r)/2;
    build(i*2+1, l, m);
    build(i*2+2, m+1, r);

}
void update(int i, int l, int r, int x, int val) {
    if(l==r) {
        seg[i] = val;
        return;
    }
    int m = (l+r)/2;
    if(x<=m) update(i*2+1, l, m, x, val);
    else update(i*2+2, m+1, r, x, val);
    seg[i] = max(seg[i*2+1], seg[i*2+2]);
}
int query(int i, int l, int r, int wl, int wr) {
    if(wl>r || wr<l) return 0;
    if(wl<=l && wr>=r) return seg[i];
    int m = (l+r)/2;
    return max(query(i*2+1, l, m, wl, wr), query(i*2+2, m+1, r, wl, wr));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    string s;
    cin>>s;
    build(0, 0, n-1);
    for(int i=0;i<n;i++) {
        if(s[i]-'0'==1) update(0, 0, n-1, i, 0);
    }
    for(int i=1;i<=q;i++) {
        cin>>s;
        if(s[0]=='q') {
            int a, b;
            cin>>a>>b;
            a--; b--;
            int q = query(0, 0, n-1, a, b-1);
            if(q==1e9) cout<<0<<'\n';
            else cout<<i-q<<'\n';
        } else {
            int a;
            cin>>a;
            a--;
            update(0, 0, n-1, a, i);
        }
    }
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

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