#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;
char str[MAXN], tmp[20];
int a[MAXN], segcnt, root[MAXN], n, q;
int seg[MAXN*18*18], L[MAXN*18*18], R[MAXN*18*18];
struct query {
int a, b, t;
bool operator<(const query rhs) const {
return a < rhs.a;
}
};
set<query> act;
void upd(int l, int r, int& k, int x, int y, int v) {
if (!k) k = ++segcnt;
if (x <= l && r <= y) { seg[k] += v; return; }
int m = (l+r) / 2;
if (x <= m) upd(l,m,L[k],x,y,v);
if (m < y) upd(m+1,r,R[k],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,L[k],x) : segqry(m+1,r,R[k],x));
}
void updF(int ind, int l, int r, int v) {
while (ind < MAXN) {
upd(1,n,root[ind],l,r,v);
ind += ind & -ind;
}
}
int qryF(int ind, int idx) {
int ret = 0;
while (ind) {
ret += segqry(1,n,root[ind],idx);
ind -= ind & -ind;
}
return ret;
}
int main() {
clock_t tim = clock();
scanf("%d %d", &n, &q);
scanf("%s", str+1);
for (int i = 1; i <= n; i++) a[i] = str[i]-'0';
for (int i = 1, j = 1; i <= n+1; i = j + 1) {
for (j = i; j <= n && a[j]; j++);
act.insert({i,j,0});
}
for (int j = 1; j <= q; j++) {
scanf("%s", tmp);
if (tmp[0] == 't') {
int idx;
scanf("%d", &idx);
if (a[idx]) {
query cur = *prev(act.lower_bound({idx+1,0,0}));
updF(cur.a, cur.a, cur.b, j-cur.t);
updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
act.erase(cur);
act.insert({cur.a,idx,j});
act.insert({idx+1,cur.b,j});
} else {
int lo = idx, hi = idx;
{
query cur = *prev(act.lower_bound({idx+1,0,0}));
lo = cur.a;
updF(cur.a, cur.a, cur.b, j-cur.t);
updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
act.erase(cur);
}
{
query cur = *prev(act.lower_bound({idx+2,0,0}));
hi = cur.b;
updF(cur.a, cur.a, cur.b, j-cur.t);
updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
act.erase(cur);
}
act.insert({lo,hi,j});
}
a[idx] ^= 1;
} else {
int lo, hi;
scanf("%d %d", &lo, &hi);
int ans = qryF(lo, hi);
query cur = *prev(act.lower_bound({lo+1,0,0}));
if (hi <= cur.b)
ans += j-cur.t;
printf("%d\n",ans);
}
}
cerr << clock() - tim << "\n";;
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:57: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:58: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", &idx);
~~~~~^~~~~~~~~~~~
street_lamps.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &lo, &hi);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
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 |
541 ms |
4672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1016 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 |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
