// Comment
//
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;
using ti = tuple<int, int, int>;
const int MAX_N = 3e5 + 100;
struct IDX {
int P; vector<int> val;
IDX(int N) {
for(P=1; P<N; P<<=1);
val = vector<int>(2*P, 0);
}
void add(int v, int k) {
val[v+=P] += k;
while(v>>=1) val[v] = val[v*2] + val[v*2+1];
}
int getSum(int a, int b) {
int res = 0;
for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
if(a%2==1) res += val[a++];
if(b%2==0) res += val[b--];
}
return res;
}
};
int N, Q;
int Nr[MAX_N];
set<ti> Lines;
vector<ti> Qs;
int Ans[MAX_N];
void addDel(vector<ti> &dels, ti del, int q) {
get<2>(del) = q - get<2>(del) + 1;
dels.push_back(del);
}
int main() {
cin >> N >> Q;
for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
for(int i=1; i<=N; i++) {
if(Nr[i] == 0) continue;
int st = i, en = i;
while(en+1 <= N && Nr[en+1] == 1) en++;
Lines.emplace(st, en, 0);
i = en;
}
for(int q=0; q<Q; q++) {
char s[10]; scanf("%s", s);
if(s[0] == 't') {
int ix; scanf("%d", &ix);
Qs.emplace_back(0, ix, -1);
}else{
int a, b; scanf("%d%d", &a, &b);
b = b-1;
Qs.emplace_back(1, a, b);
}
}
vector<ti> dels;
vector<ti> queries;
for(int q=0; q<Q; q++) {
char s[10]; scanf("%s", s);
if(get<0>(Qs[q]) == 0) {
int ix = get<1>(Qs[q]);
if(Nr[ix] == 0) {
int lv = Nr[ix-1], rv = Nr[ix+1];
int l = ix, r = ix;
auto it = Lines.begin();
if(lv) {
it = Lines.lower_bound(ti(ix, -INF, -INF));
it--;
l = get<0>(*it);
Lines.erase(it);
addDel(dels, *it, q);
}
if(rv) {
it = Lines.lower_bound(ti(ix, -INF, -INF));
r = get<1>(*it);
Lines.erase(it);
addDel(dels, *it, q);
}
Lines.emplace(ti(l, r, q+1));
}else{
auto it = Lines.lower_bound(ti(ix+1, -INF, -INF));
it--;
int l, r; tie(l, r, ignore) = *it;
Lines.erase(it);
addDel(dels, *it, q);
if(l <= ix-1) Lines.emplace(ti(l, ix-1, q+1));
if(r >= ix+1) Lines.emplace(ti(ix+1, r, q+1));
}
Nr[ix] = 1 - Nr[ix];
}else{
int a, b; tie(ignore, a, b) = Qs[q];
queries.emplace_back(a, b, q);
}
}
sort(ALL(dels));
sort(ALL(queries));
int delsIx = 0;
IDX idx = IDX(N+1);
for(ti query: queries) {
int a, b, q; tie(a, b, q) = query;
while(delsIx < SZ(dels) && get<0>(dels[delsIx]) <= a) {
int x, y, v; tie(x, y, v) = dels[delsIx++];
idx.add(y, v);
}
int now = idx.getSum(b, N);
//if(now != 0) printf(">> [%d] %d %d += %d\n", q, a, b, now);
Ans[q] += now;
}
for(ti query: queries) {
int a, b, q; tie(a, b, q) = query;
if(SZ(Lines) == 0) continue;
auto it = Lines.lower_bound(ti(a+1, -INF, -INF));
it--;
int x, y, t; tie(x, y, t) = *it;
if(x <= a && b <= y) {
//if(q-t+1 != 0) printf("<< [%d] %d %d += %d (%d)\n", q, a, b, q-t+1, t);
Ans[q] += q - t + 1;
}
}
for(int q=0; q<Q; q++) {
if(get<0>(Qs[q]) == 1) {
printf("%d\n", Ans[q]);
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:53:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
| ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:63:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
63 | char s[10]; scanf("%s", s);
| ~~~~~^~~~~~~~~
street_lamps.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
65 | int ix; scanf("%d", &ix);
| ~~~~~^~~~~~~~~~~
street_lamps.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | int a, b; scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:77:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | char s[10]; scanf("%s", s);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
13252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
408 ms |
25408 KB |
Output is correct |
| 6 |
Correct |
448 ms |
27992 KB |
Output is correct |
| 7 |
Correct |
502 ms |
26160 KB |
Output is correct |
| 8 |
Correct |
545 ms |
23256 KB |
Output is correct |
| 9 |
Correct |
338 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
282 ms |
16080 KB |
Output is correct |
| 11 |
Correct |
288 ms |
14296 KB |
Output is correct |
| 12 |
Correct |
279 ms |
15960 KB |
Output is correct |
| 13 |
Correct |
293 ms |
14296 KB |
Output is correct |
| 14 |
Correct |
278 ms |
16088 KB |
Output is correct |
| 15 |
Correct |
347 ms |
20700 KB |
Output is correct |
| 16 |
Correct |
356 ms |
22028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
