#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = (int)3e5 + 7;
int n, q;
struct fen {
ll tree[N];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val) {
while (pos <= n) {
tree[pos] += val;
pos |= (pos + 1);
}
}
ll get(int r) {
ll res = 0;
while (r >= 0) {
res += tree[r];
r = (r & (r + 1)) - 1;
}
return res;
}
ll get(int l, int r) {
return get(r) - get(l - 1);
}
};
fen pr;
struct T {
int tree[N * 4];
T() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val, int v = 1, int tl = 0, int tr = n - 1) {
if (tl == tr) {
tree[v] = val;
return ;
}
int mid = (tl + tr) >> 1;
if (pos <= mid)
upd(pos, val, v + v, tl, mid);
else
upd(pos, val, v + v + 1, mid + 1, tr);
tree[v] = max(tree[v + v], tree[v + v + 1]);
}
int get(int l, int r, int v = 1, int tl = 0, int tr = n - 1) {
if (tl > r || tr < l) return -1;
if (l <= tl && tr <= r) return tree[v];
int mid = (tl + tr) >> 1;
return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}
};
T tr;
string s;
int cnt[N];
int lst[N];
int ans[N], tp[N];
pair<int, int> get(int s) {
int S = s;
for (int i = 18; i >= 0; i--) {
if (pr.get(max(s - (1 << i), 1), s) == s - max(s - (1 << i), 1) + 1) {
s = max(s - (1 << i), 1);
}
}
int Left = s;
s = S;
for (int i = 18; i >= 0; i--) {
if (pr.get(s, min(s + (1 << i), n)) == min(s + (1 << i), n) - s + 1) {
s = min(s + (1 << i), n);
}
}
int Right = s;
return {Left, Right};
}
main() {
scanf("%d %d", &n, &q);
cin >> s;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
lst[i] = -1;
pr.upd(i, 1);
}
tr.upd(i, lst[i]);
}
for (int i = 1; i <= q; i++) {
string tp;
cin >> tp;
if (tp[0] == 't') {
int ind;
scanf("%d", &ind); ind--;
s[ind] ^= 1;
if (s[ind] == '1') {
lst[ind] = i - 1;
tr.upd(ind, lst[ind]);
pr.upd(ind, 1);
} else {
pair<int, int> ar = get(ind);
pr.upd(ind, -1);
// ******
}
} else {
tp[i] = 1;
int a, b;
scanf("%d %d", &a, &b); a--; b--;
if (pr.get(a, b - 1) == b - a) {
ans[i] += (i - tr.get(a, b - 1) - 1);
}
}
}
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
Compilation message
street_lamps.cpp:85:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:107:20: warning: variable 'ar' set but not used [-Wunused-but-set-variable]
pair<int, int> ar = get(ind);
^~
street_lamps.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ind); ind--;
~~~~~^~~~~~~~~~~~
street_lamps.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b); a--; b--;
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
