#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const int BLOCK = 3000;
char str[MAXN], tmp[20];
int sm[MAXN], a[MAXN], ans[MAXN];
int nx[MAXN], val[MAXN];
int seg[MAXN*4];
struct query {
int t, a, b;
} qry[MAXN];
struct sweep {
int t, a, b, val;
bool operator<(const sweep rhs) const {
if (rhs.b == b) return t < rhs.t;
return b > rhs.b;
}
};
map<sweep,int> cparr;
void build(int l, int r, int k) {
seg[k] = 0;
if (l == r) return;
int m = (l+r) / 2;
build(l,m,k*2);
build(m+1,r,k*2+1);
}
void upd(int l, int r, int k, int x, int y, int v) {
if (x <= l && r <= y) { seg[k] += v; return; }
int m = (l+r) / 2;
if (x <= m) upd(l,m,k*2,x,y,v);
if (m < y) upd(m+1,r,k*2+1,x,y,v);
}
int segqry(int l, int r, int k, int x) {
if (x <= l && r <= x) return seg[k];
int m = (l+r) / 2;
return seg[k] + (x <= m ? segqry(l,m,k*2,x) : segqry(m+1,r,k*2+1,x));
}
int main() {
clock_t tim = clock();
sm[0] = 0;
int n, q; scanf("%d %d", &n, &q);
scanf("%s", str+1);
for (int i = 1; i <= n; i++) a[i] = str[i]-'0', val[i] = a[i];
for (int j = 1; j <= q; j++) {
scanf("%s", tmp);
if (tmp[0] == 't') {
qry[j].t = 1;
scanf("%d", &qry[j].a);
} else {
qry[j].t = 2;
scanf("%d %d", &qry[j].a, &qry[j].b);
}
}
map<pii,int> act;
for (int j = 1; j <= n; j++) {
if (a[j] == 0) continue;
int k = j;
for (; k <= n && a[k] == 1; k++);
act[mp(j,k-1)] = 1;
nx[j] = k-1;
nx[k-1] = j;
j = k-1;
}
int curm = 0;
for (int i = 1; i <= q; i += BLOCK) {
for (int j = max(1,i-BLOCK); j < i; j++) {
if (qry[j].t == 2) continue;
int ind = qry[j].a;
if (!val[ind]) {
int lo = ind, hi = ind;
if (val[ind-1]) {
lo = nx[ind-1];
auto it = act.find(mp(lo,ind-1));
cparr[{1, lo, ind-1, 0}] += j-it->se+1;
act.erase(it);
nx[ind-1] = 0;
}
if (val[ind+1]) {
hi = nx[ind+1];
auto it = act.find(mp(ind+1,hi));
cparr[{1, ind+1, hi, 0}] += j-it->se+1;
act.erase(it);
nx[ind+1] = 0;
}
act[mp(lo,hi)] = j+1;
nx[lo] = hi;
nx[hi] = lo;
} else {
auto it = prev(act.upper_bound(mp(ind,INF)));
int lo = it->fi.fi, hi = it->fi.se;
cparr[{1, lo, hi, 0}] += j-it->se+1;
act.erase(it);
nx[lo] = nx[hi] = 0;
if (lo < ind) {
act[mp(lo,ind-1)] = j+1;
nx[lo] = ind-1;
nx[ind-1] = lo;
}
if (ind < hi) {
act[mp(ind+1,hi)] = j+1;
nx[ind+1] = hi;
nx[hi] = ind+1;
}
}
val[ind] ^= 1;
}
for (int j = 1; j <= n; j++) sm[j] = sm[j-1] + a[j];
for (int j = i; j <= min(q,i+BLOCK-1); j++) {
if (qry[j].t == 1) continue;
cparr[{2, qry[j].a, qry[j].b-1, j}] = j;
int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
int ind = cur == qry[j].b-qry[j].a ? i : j;
if (!act.empty()) {
auto it = act.upper_bound(mp(qry[j].a,INF));
if (it != act.begin()) {
it = prev(it);
if (it->fi.fi <= qry[j].a && qry[j].b-1 <= it->fi.se)
ans[j] += ind-it->se+1;
}
}
vector<int> x;
for (int k = i; k < j; k++) {
if (qry[k].t == 1 && qry[j].a <= qry[k].a && qry[k].a < qry[j].b) {
x.pb(qry[k].a);
a[qry[k].a] ^= 1;
cur += 2*a[qry[k].a]-1;
}
ans[j] += (int)(cur == qry[j].b-qry[j].a);
}
for (auto j: x) a[j] ^= 1;
}
build(1,n,1);
for (auto it: cparr) {
sweep cur = it.fi;
if (cur.t == 1)
upd(1,n,1,cur.a,cur.b,it.se);
else
ans[it.se] += segqry(1,n,1,cur.a);
}
for (int j = i; j <= min(q,i+BLOCK-1); j++)
if (qry[j].t == 1)
a[qry[j].a] ^= 1;
else {
cparr.erase({2, qry[j].a, qry[j].b-1, j});
printf("%d\n", ans[j]);
}
}
//cerr << clock() - tim << "\n";
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:54:10: warning: unused variable 'tim' [-Wunused-variable]
clock_t tim = clock();
^~~
street_lamps.cpp:79:6: warning: unused variable 'curm' [-Wunused-variable]
int curm = 0;
^~~~
street_lamps.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q; scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str+1);
~~~~~^~~~~~~~~~~~~
street_lamps.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", tmp);
~~~~~^~~~~~~~~~~
street_lamps.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &qry[j].a);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &qry[j].a, &qry[j].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1771 ms |
6668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
504 KB |
Output is correct |
| 4 |
Correct |
4 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2626 ms |
26104 KB |
Output is correct |
| 6 |
Correct |
4246 ms |
25472 KB |
Output is correct |
| 7 |
Incorrect |
4797 ms |
22972 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2065 ms |
20996 KB |
Output is correct |
| 6 |
Correct |
3315 ms |
24448 KB |
Output is correct |
| 7 |
Correct |
3489 ms |
26688 KB |
Output is correct |
| 8 |
Correct |
3292 ms |
28456 KB |
Output is correct |
| 9 |
Incorrect |
515 ms |
5496 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
1771 ms |
6668 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
