#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef cc_hash_table<int,null_type,hash<int>> ht;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const int BLOCK = 4000;
char str[MAXN], tmp[20];
int sm[MAXN], a[MAXN], ans[MAXN];
int nx[MAXN], val[MAXN];
int seg[MAXN*4], nxu[MAXN];
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;
}
};
multiset<sweep> 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];
int p = 0;
for (int j = 1; j <= q; j++) {
scanf("%s", tmp);
if (tmp[0] == 't') {
qry[j].t = 1;
scanf("%d", &qry[j].a);
nxu[p] = j;
p = j;
} else {
qry[j].t = 2;
scanf("%d %d", &qry[j].a, &qry[j].b);
}
}
nxu[p] = q;
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.insert({1, lo, ind-1, 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.insert({1, ind+1, hi, 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.insert({1, lo, hi, 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;
}
int m = 0;
multiset<sweep> arr = cparr;
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;
arr.insert({2, qry[j].a, qry[j].b-1, j});
int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
int ind = j;
if (cur == qry[j].b-qry[j].a)
ind = i;
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;
}
if (cur == qry[j].b-qry[j].a)
ans[j]++;
}
for (auto j: x)
a[j] ^= 1;
}
build(1,n,1);
for (auto cur: arr) {
if (cur.t == 1) // upd
upd(1,n,1,cur.a,cur.b,cur.val);
else
ans[cur.val] += 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
printf("%d\n", ans[j]);
}
cerr << clock() - tim << "\n";
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:130:7: warning: unused variable 'm' [-Wunused-variable]
int m = 0;
^
street_lamps.cpp:87:6: warning: unused variable 'curm' [-Wunused-variable]
int curm = 0;
^~~~
street_lamps.cpp:60: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:61: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:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", tmp);
~~~~~^~~~~~~~~~~
street_lamps.cpp:68: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:73: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 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4347 ms |
29456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
