Submission #1182133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182133		thangdz2k7	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1136 ms	161716 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e5 + 5;

int n, q;
set <int> off;
int nNode = 0, root[MAX], st[MAX * 100], lf[MAX * 100], rg[MAX * 100];

void update(int &s, int l, int r, int u, int v, int val){
    if (!s) s = ++ nNode;
    if (u <= l && r <= v){
        st[s] += val;
        return;
    }

    int mid = l + r >> 1;

    if (mid >= u) update(lf[s], l, mid, u, v, val);
    if (mid < v) update(rg[s], mid + 1, r, u, v, val);
}

void add2d(int l, int r, int u, int v, int val){
    for (int p = l; p <= n; p += p & -p)
        update(root[p], 2, n + 1, u, v, val);
    for (int p = r + 1; p <= n; p += p & -p)
        update(root[p], 2, n + 1, u, v, -val);
}

int get(int s, int l, int r, int u){
    if (!s) return 0;
    if (l == r) return st[s];

    int mid = l + r >> 1;
    if (mid >= u) return get(lf[s], l, mid, u) + st[s];
    return get(rg[s], mid + 1, r, u) + st[s];
}

int get2d(int a, int b){
    int ans = 0;
    for (; a; a -= a & -a)
        ans += get(root[a], 2, n + 1, b);

    return ans;
}

void process(){
    cin >> n >> q;
    string s;
    cin >> s; s = ' ' + s;

    off.insert(0); off.insert(n + 1);
    for (int i = 1; i <= n; ++ i)
        if (s[i] == '0') off.insert(i);

    for (int timer = 1; timer <= q; ++ timer){
        string op; cin >> op;
        if (op == "toggle"){
            int i; cin >> i;
            if (off.find(i) != off.end()){
                off.erase(i);
                auto it = off.upper_bound(i);
                int r = *it; it --;
                int l = *it; l ++;
                add2d(l, i, i + 1, r, -timer);
            }

            else {
                auto it = off.upper_bound(i);
                int r = *it; it --;
                int l = *it; l ++;
                off.insert(i);
                add2d(l, i, i + 1, r, timer);
            }
        }

        else {
            int a, b; cin >> a >> b;
            int ans = get2d(a, b);
            if (*off.lower_bound(a) >= b) ans += timer;
            cout << ans << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    process();
    return 0;
}

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