Submission #1234254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234254		clemmy14	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	403 ms	5156 KiB

street_lamps

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

struct SegTreeMax {
    int n; vector<int> s;
    SegTreeMax(int n) : s(2*n), n(n) {}
    void update(int pos, int val) {
        for(s[pos+=n]=val; pos/=2;) {
            s[pos]=max(s[pos*2], s[pos*2+1]);
        }
    }
    int query(int b, int e) {
        int ra=0, rb=0;
        for(b+=n, e+=n; b<e; b/=2, e/=2) {
            if(b%2) ra=max(ra, s[b++]);
            if(e%2) rb=max(rb, s[--e]);
        }
        return max(ra, rb);
    }
};

signed main() {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    SegTreeMax segmax(n);
    for(int i=0; i<n; i++) {
        if(s[i] == '0') segmax.update(i, 1e9);
        else segmax.update(i, 0);
    }
    int time=1;
    while(q--) {
        string t; cin >> t;
        if(t == "query") {
            int a, b; cin >> a >> b; a--; b--;
            int last=segmax.query(a, b);
            if(last == 1e9) cout << "0\n";
            else cout << time-last << '\n';
        } else {
            int i; cin >> i; i--;
            segmax.update(i, time);
        }
        time++;
    }
    return 0;
}

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