Submission #1182140

#TimeUsernameProblemLanguageResultExecution timeMemory
1182140thangdz2k7Street Lamps (APIO19_street_lamps)C++20
100 / 100
1089 ms161620 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimzie ("unroll-loops") using namespace std; const int MAX = 3e5 + 5; int n, q; set <int> off; int nNode = 0, root[MAX], st[MAX * 80], lf[MAX * 80], rg[MAX * 80]; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...