#include <bits/stdc++.h>
using namespace std;
#define app push_back
const int N = 3e5 + 7;
struct Quer {
int t, i, l, r;
};
struct Fen {
int w, l, cnt;
Fen() {
w = 0; l = 0; cnt = 0;
}
};
struct Event {
int t, l, r, tm;
};
int n, q;
bool a[N];
Quer d[N];
vector <int> f[N];
vector <Event> mem;
void add(int l, int r, int t) {
r = n - r;
mem.app({1, l, r, t});
for (int i = l; i < N; i |= i + 1) {
f[i].app(r);
}
}
int cl[N], cr[N];
int sum[N << 2];
void build(int v, int tl, int tr) {
if (tl == tr) {
sum[v] = a[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}
void upd(int v, int tl, int tr, int p, int x) {
if (tr == tl) {
sum[v] = x;
return;
}
int tm = (tl + tr) >> 1;
if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
else upd(v * 2 + 2, tm + 1, tr, p, x);
sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}
int getl(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl || sum[v] == tr - tl + 1) return n;
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
int t = getl(v * 2 + 1, tl, tm, l, r);
if (t != n) return t;
else return getl(v * 2 + 2, tm + 1, tr, l, r);
}
int getr(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl || sum[v] == tr - tl + 1) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
int t = getr(v * 2 + 2, tm + 1, tr, l, r);
if (t != -1) return t;
else return getr(v * 2 + 1, tl, tm, l, r);
}
vector <Fen> fn[N];
void add1(int x, int y, int t) {
for (int i = x; i < N; i |= i + 1) {
int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
for (; j < fn[i].size(); j |= j + 1) {
fn[i][j].l += t;
fn[i][j].cnt++;
}
}
}
void del1(int x, int y, int t) {
for (int i = x; i < N; i |= i + 1) {
int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
for (; j < fn[i].size(); j |= j + 1) {
fn[i][j].l -= t;
fn[i][j].cnt--;
}
}
}
void add2(int x, int y, int t) {
for (int i = x; i < N; i |= i + 1) {
int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
for (; j < fn[i].size(); j |= j + 1) {
fn[i][j].w += t;
}
}
}
int get(int x, int y, int t) {
int ans = 0;
for (int i = x; i >= 0; i &= i + 1, --i) {
int j = upper_bound(f[i].begin(), f[i].end(), y) - f[i].begin() - 1;
for (; j >= 0; j &= j + 1, --j) {
ans += fn[i][j].w;
ans -= fn[i][j].l;
ans += fn[i][j].cnt * t;
}
}
return ans;
}
map <int, int> dc[N];
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> q;
for (int i = 0; i < n; ++i) {
char c;
cin >> c;
a[i] = c == '1';
}
for (int i = 0; i < q; ++i) {
string t;
cin >> t;
if (t == "toggle") {
d[i].t = 1;
cin >> d[i].i;
--d[i].i;
}
else {
d[i].t = 2;
cin >> d[i].l >> d[i].r;
--d[i].r;
--d[i].l; --d[i].r;
}
}
int l = -1;
for (int i = 0; i < n; ++i) {
if (!a[i]) {
if (l != -1) {
add(l, i - 1, 0);
l = -1;
}
}
else {
if (l == -1) {
l = i;
}
}
}
if (a[n - 1]) {
add(l, n - 1, 0);
}
build(0, 0, n - 1);
for (int i = 0; i < q; ++i) {
if (d[i].t == 1) {
int p = d[i].i;
if (a[p]) {
int l = getr(0, 0, n - 1, 0, p - 1) + 1;
int r = getl(0, 0, n - 1, p + 1, n - 1) - 1;
mem.app({2, l, n - r, i + 1});
if (l != p) {
add(l, p - 1, i + 1);
}
if (r != p) {
add(p + 1, r, i + 1);
}
}
else {
int l = getr(0, 0, n - 1, 0, p - 1) + 1;
int r = getl(0, 0, n - 1, p + 1, n - 1) - 1;
if (l != p) {
mem.app({2, l, n - (p - 1), i + 1});
}
if (r != p) {
mem.app({2, p + 1, n - r, i + 1});
}
add(l, r, i + 1);
}
}
else {
mem.app({3, d[i].l, n - d[i].r, i + 1});
}
}
for (int i = 0; i < N; ++i) {
sort(f[i].begin(), f[i].end());
f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin());
}
for (int i = 0; i < N; ++i) {
fn[i].resize(f[i].size());
}
for (auto e : mem) {
if (e.t == 1) {
add1(e.l, e.r, e.tm);
dc[e.l][e.r] = e.tm;
}
else if (e.t == 2) {
int pr = dc[e.l][e.r];
del1(e.l, e.r, pr);
add2(e.l, e.r, e.tm - pr);
}
else {
cout << get(e.l, e.r, e.tm) << '\n';
}
}
}
Compilation message
street_lamps.cpp: In function 'void add1(int, int, int)':
street_lamps.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; j < fn[i].size(); j |= j + 1) {
~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'void del1(int, int, int)':
street_lamps.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; j < fn[i].size(); j |= j + 1) {
~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'void add2(int, int, int)':
street_lamps.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; j < fn[i].size(); j |= j + 1) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
463 ms |
58196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
28920 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
28792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
28664 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
28792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
28536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
