Submission #903805

#TimeUsernameProblemLanguageResultExecution timeMemory
903805Trisanu_DasStreet Lamps (APIO19_street_lamps)C++17
100 / 100
2327 ms72000 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; struct Query { bool isToggle; int left, right, time, delta; }; const int N = 1 << 19; Query a[3 * N], b[3 * N]; int q, ans[N]; void cdq2(int l, int r) { if (r - l == 1) return; int m = (l + r) >> 1; cdq2(l, m); cdq2(m, r); for (int i = l; i < r; ++i) b[i].right = i < m; inplace_merge(b + l, b + m, b + r, [&](Query a, Query b) { return a.time < b.time; }); int s = 0; for (int i = l; i < r; ++i) { if (!b[i].isToggle && b[i].left && b[i].right) s += b[i].delta * b[i].time; if (b[i].isToggle && !b[i].left && !b[i].right) ans[b[i].time] += s; } } void cdq1(int l, int r) { if (r - l == 1) return; int m = (l + r) >> 1; cdq1(l, m); cdq1(m, r); for (int i = l; i < r; ++i) a[i].left = i < m; merge(a + l, a + m, a + m, a + r, b + l, [&](Query a, Query b) { return pair(-a.right, a.isToggle) < pair(-b.right, b.isToggle); }); for (int i = l; i < r; ++i) a[i] = b[i]; cdq2(l, r); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, p = 0; cin >> n >> q; int pre = -1; set<int> z = {-1}; for (int i = 0; i < n; ++i) { char c; cin >> c; if (c != '0') { if (p && a[p - 1].right == i) a[p - 1].right = i + 1; else a[p++] = {0, pre + 1, i + 1, -1, -1}; } else { z.insert(pre = i); } } z.insert(n); for (int t = 0; t < q; ++t) { string s; cin >> s; if (s == "toggle") { int i; cin >> i; --i; auto [it, f] = z.insert(i); int d = f ? +1 : -1; a[p++] = {0, *prev(it) + 1, *next(it), t, +d}; a[p++] = {0, *prev(it) + 1, i, t, -d}; a[p++] = {0, i + 1, *next(it), t, -d}; if (d < 0) z.erase(it); ans[t] = -1; } else { int l, r; cin >> l >> r; --l; --r; a[p++] = {1, l, r, t, 0}; ans[t] = *z.lower_bound(l) < r ? 0 : t; } } sort(a, a + p, [&](Query a, Query b) { return pair(a.left, a.isToggle) < pair(b.left, b.isToggle); }); cdq1(0, p); for (int t = 0; t < q; ++t) if (0 <= ans[t]) cout << ans[t] << '\n'; 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...