#include <bits/stdc++.h>
using namespace std;
/*struct Implicit {
vector <int> tree, tl, tr; int cnt;
int create () {
++cnt; tl.push_back(-1); tr.push_back(-1); tree.push_back(0); return cnt;
}
void init () {
tree.push_back(0); tl.push_back(-1); tr.push_back(-1); cnt = 0;
}
void update (int l, int r, int a, int b, int node) {
if (l == r) {
tree[node] += b; return;
}
int mid = (l + r) >> 1;
if (a <= mid) {
if (tl[node] == -1) tl[node] = create();
else tree[node] -= tree[tl[node]];
update(l, mid, a, b, tl[node]);
tree[node] += tree[tl[node]];
} else {
if (tr[node] == -1) tr[node] = create();
else tree[node] -= tree[tr[node]];
update(mid + 1, r, a, b, tr[node]);
tree[node] += tree[tr[node]];
}
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
int sum = 0, mid = (l + r) >> 1;
if (tl[node] != -1) sum += get(l, mid, a, b, tl[node]);
if (tr[node] != -1) sum += get(mid + 1, r, a, b, tr[node]);
return sum;
}
};*/
typedef long long ll;
const int MAXN = 3e5 + 25;
bool a[MAXN];
int n, q;
set <array <int, 3>> cur;
void init () {
for (int i = 1; i <= n; i++) {
if (!a[i]) continue;
int j = i; while (j + 1 <= n && a[j + 1]) j++;
cur.insert({i, j, 0});
i = j;
}
}
vector <array <int, 3>> inserted;
void add (array <int, 3> x, int y) {
cur.erase(x);
inserted.push_back({x[0], x[1], y - x[2]});
}
void insert (array <int, 3> x) {
cur.insert(x);
}
int query (int l, int r, int x) {
int sum = 0;
for (auto i : inserted) if (i[0] <= l && r <= i[1]) sum += i[2];
// auto z = cur.upper_bound({l, r, 0});
// if (z != cur.begin()) {
for (auto g : cur) {
// z--; auto g = *z; cout << g[0] << " " << g[1] << '\n';
if (g[0] <= l && r <= g[1]) sum += x - g[2];
}
return sum;
}
int main () {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
char x; cin >> x; a[i] = x == '1';
}
init();
for (int t = 1; t <= q; t++) {
string x; cin >> x;
if (x == "query") {
int l, r; cin >> l >> r; r--;
cout << query(l, r, t) << '\n';
} else {
int x; cin >> x; a[x] ^= 1;
if (!a[x]) {
auto z = *(--cur.upper_bound({x, 0}));
add(z, t);
auto l = z; l[2] = t + 1; l[1] = x - 1;
if (l[0] <= l[1]) insert(l);
l = z; l[2] = t + 1; l[0] = x + 1;
if (l[0] <= l[1]) insert(l);
} else {
int mn = x, mx = x;
if (x < n && a[x + 1]) {
auto z = *(cur.lower_bound({x + 1, 0}));
add(z, t);
mx = z[1];
}
if (x > 1 && a[x - 1]) {
auto z = *(--cur.lower_bound({x, 0}));
add(z, t);
mn = z[0];
}
array <int, 3> z = {mn, mx, t};
insert(z);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5048 ms |
3028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Correct |
3 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3906 ms |
16560 KB |
Output is correct |
| 6 |
Execution timed out |
5048 ms |
6592 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
