#include <stdio.h>
#include <string.h>
#define N 300000
#define Q 300000
#define M (Q * 3)
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
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], ll1[Q], rr1[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_ = ll1[l], m_ = ll1[m], r_ = rr1[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 zz[1 + N + Q], ll[1 + N + Q], rr[1 + N + Q], ii[1 + N + Q], u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i;
return _++;
}
void split(int u, int i) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (ii[u] < i) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (ii[u] > i) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int first(int u) {
return ll[u] == 0 ? u : first(ll[u]);
}
int last(int u) {
return rr[u] == 0 ? u : last(rr[u]);
}
int main() {
static char cc[N + 1];
int q, m, h, i;
scanf("%d%d%s", &n, &q, cc);
for (i = 0; i < n; i++)
if (cc[i] == '1')
update(i, 1);
else
u_ = merge(u_, node(i));
m = 0;
for (h = 0; h < q; h++) {
static char s[8];
scanf("%s", s);
ll1[h] = m;
if (s[0] == 't') {
int p, q;
scanf("%d", &i), i--;
split(u_, i), p = l_ ? ii[last(l_)] + 1 : 0, q = r_ ? ii[first(r_)] - 1 : n - 1;
type[h] = 1;
if (cc[i] == '0') {
cc[i] = '1';
u_ = merge(l_, r_);
if (p < i)
ll_[m] = p, rr_[m] = i - 1, xx[m] = h + 1, m++;
if (i < q)
ll_[m] = i + 1, rr_[m] = q, xx[m] = h + 1, m++;
update(i, 1);
} else {
cc[i] = '0';
u_ = merge(merge(l_, node(i)), r_);
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++;
if (i < q)
ll_[m] = i + 1, rr_[m] = q, xx[m] = -(h + 1), m++;
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;
}
rr1[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:130:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d%d%s", &n, &q, cc);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.c:140:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%s", s);
| ^~~~~~~~~~~~~~
street_lamps.c:145:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
street_lamps.c:169:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
169 | 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 |
356 ms |
15156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
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 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 4 |
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 |
- |
