#include <stdio.h>
#include <string.h>
#define N 300000
#define Q 300000
#define M (Q * 3)
int ft[N], n;
void update(int i, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int type[Q], ll_[Q], rr_[Q], ans[Q];
int ll[M], rr[M], xx[M], hh[M], hh_[M];
void merge(int l, int m, int r) {
int i, j, k;
i = l, j = m, k = l;
while (i < m && j < r)
hh_[k++] = rr[hh[i]] < rr[hh[j]] ? hh[i++] : hh[j++];
while (i < m)
hh_[k++] = hh[i++];
while (j < r)
hh_[k++] = hh[j++];
memcpy(hh + l, hh_ + l, (r - l) * sizeof *hh_);
}
void solve(int l, int r) {
int m, l_, m_, r_, i, j;
if (r - l == 1)
return;
m = (l + r) / 2;
solve(l, m), solve(m, r);
l_ = ll_[l], m_ = ll_[m], r_ = rr_[r - 1];
for (j = r_ - 1, i = m_ - 1; j >= m_; j--) {
int hi, hj = hh[j];
while (i >= l_ && rr[hi = hh[i]] >= rr[hj]) {
if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
update(ll[hi], xx[hi]);
i--;
}
if (xx[hj] > 0 && type[xx[hj] - 1] == 2)
ans[xx[hj] - 1] += query(ll[hj]);
}
while (++i < m_) {
int hi = hh[i];
if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
update(ll[hi], -xx[hi]);
}
merge(l_, m_, r_);
}
int main() {
static char cc[N + 1];
static int pp[N], qq[N];
int q, m, h, i;
scanf("%d%d%s", &n, &q, cc);
for (i = 0; i < n; i++)
if (cc[i] == '1') {
int p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i;
pp[i] = p, qq[p] = i;
update(i, 1);
}
m = 0;
for (h = 0; h < q; h++) {
static char s[8];
scanf("%s", s);
ll_[h] = m;
if (s[0] == 't') {
int p, q;
scanf("%d", &i), i--;
type[h] = 1;
if (cc[i] == '0') {
cc[i] = '1';
p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i, q = i + 1 < n && cc[i + 1] == '1' ? qq[i + 1] : i;
if (p < i)
ll[m] = p, rr[m] = i - 1, xx[m] = h + 1, m++;
ll[m] = p, rr[m] = q, xx[m] = -(h + 1), m++;
qq[p] = q, pp[q] = p;
if (i < q)
ll[m] = i + 1, rr[m] = q, xx[m] = h + 1, m++;
update(i, 1);
} else {
cc[i] = '0';
p = pp[i], q = qq[i];
if (p < i) {
ll[m] = p, rr[m] = i - 1, xx[m] = -(h + 1), m++;
qq[p] = i - 1, pp[i - 1] = p;
}
ll[m] = p, rr[m] = q, xx[m] = h + 1, m++;
if (i < q) {
ll[m] = i + 1, rr[m] = q, xx[m] = -(h + 1), m++;
qq[i + 1] = q, pp[q] = i + 1;
}
update(i, -1);
}
} else {
int l, r;
scanf("%d%d", &l, &r), l--, r -= 2;
type[h] = 2;
ll[m] = l, rr[m] = r, xx[m] = h + 1, m++;
if (query(r) - query(l - 1) == r - l + 1)
ans[h] += h + 1;
}
rr_[h] = m;
}
for (h = 0; h < m; h++)
hh[h] = h;
memset(ft, 0, n * sizeof *ft);
solve(0, q);
for (h = 0; h < q; h++)
if (type[h] == 2)
printf("%d\n", ans[h]);
return 0;
}
Compilation message
street_lamps.c: In function 'main':
street_lamps.c:76:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%d%d%s", &n, &q, cc);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.c:88:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%s", s);
| ^~~~~~~~~~~~~~
street_lamps.c:93:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
street_lamps.c:122:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
122 | scanf("%d%d", &l, &r), l--, r -= 2;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
15320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
559 ms |
20716 KB |
Output is correct |
| 6 |
Correct |
611 ms |
20356 KB |
Output is correct |
| 7 |
Correct |
551 ms |
19052 KB |
Output is correct |
| 8 |
Correct |
346 ms |
15596 KB |
Output is correct |
| 9 |
Correct |
150 ms |
9836 KB |
Output is correct |
| 10 |
Correct |
163 ms |
10604 KB |
Output is correct |
| 11 |
Correct |
162 ms |
10860 KB |
Output is correct |
| 12 |
Correct |
328 ms |
13036 KB |
Output is correct |
| 13 |
Correct |
347 ms |
15724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
