Submission #721779

#	Time	Username	Problem	Language	Result	Execution time	Memory
721779		GrandTiger1729	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	503 ms	31044 KiB

street_lamps

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

const int INF = 1e9;
struct SegTree {
    int l, r, mid;
    int val = INF;
    SegTree *lc, *rc;
    SegTree(int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1) return;
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    void pull(){
        val = max(lc->val, rc->val);
    }
    void update(int i, int u){
        if (l == r - 1)
            return void(val = u);
        if (i < mid)
            lc->update(i, u);
        else
            rc->update(i, u);
        pull();
    }
    int query(int ll, int rr){
        if (ll <= l && rr >= r)
            return val;
        int ret = -INF;
        if (ll < mid)
            ret = max(ret, lc->query(ll, rr));
        if (mid < rr)
            ret = max(ret, rc->query(ll, rr));
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<bool> a(n);
    for (int i = 0; i < n; i++){
        char c; cin >> c;
        a[i] = c - '0';
    }
    SegTree st(0, n);
    for (int i = 0; i < n; i++)
        if (a[i])
            st.update(i, 0);
    for (int qq = 1; qq <= q; qq++){
        string ty; cin >> ty;
        if (ty == "toggle"){
            int i; cin >> i;
            i--;
            st.update(i, qq);
        }else{
            int l, r; cin >> l >> r;
            l--, r--;
            cout << max(0, qq - st.query(l, r)) << '\n';
        }
    }
    return 0;
}

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