This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |