// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 3e5 + 10, MOD = 1e9 + 7;
vector<int> F[N], vec[N]; set<pair<pii, int>> st, tmp;
int n, q, A[N], type[N], ql[N], qr[N]; char C[N];
void __init(int r, int c) {
for (; r < N; r += r & -r) vec[r].push_back(c);
}
void init(int r, int c) {
__init(r, r), __init(c + 1, c + 1), __init(r, c + 1), __init(c + 1, r);
}
void __upd(int r, int c, int x) {
for (; r < N; r += r & -r) {
int _c = lower_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin();
for (; _c < SZ(F[r]); _c += _c & -_c) F[r][_c] += x;
}
}
void upd(int r, int c, int x) {
__upd(r, r, x), __upd(c + 1, c + 1, x), __upd(r, c + 1, -x), __upd(c + 1, r, -x);
}
int get(int r, int c) {
int ret = 0;
for (; r; r -= r & -r) {
int _c = upper_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin() - 1;
for (; _c; _c -= _c & -_c) ret += F[r][_c];
}
return ret;
}
void __erase(int x) {
auto it = st.upper_bound({{x, MOD}, 0});
it--;
int l = it->F.F, r = it->F.S;
init(l, r); st.erase(it);
if (x > l) st.insert({{l, x - 1}, 0});
if (x < r) st.insert({{x + 1, r}, 0});
}
void __add(int x) {
int l = x, r = x;
auto it = st.upper_bound({{x, MOD}, 0});
if (it != st.end()) {
if (it->F.F == x + 1) {
init(x + 1, it->F.S); r = it->F.S, st.erase(it);
}
}
it = st.upper_bound({{x, MOD}, 0});
if (it != st.begin()) {
it--;
if (it->F.S == x - 1) {
init(it->F.F, x - 1); l = it->F.F, st.erase(it);
}
}
st.insert({{l, r}, 0});
}
void add(int x, int id) {
int l = x, r = x;
auto it = st.upper_bound({{x, MOD}, 0});
if (it != st.end()) {
if (it->F.F == x + 1) {
upd(x + 1, it->F.S, id - it->S), r = it->F.S, st.erase(it);
}
}
it = st.upper_bound({{x, MOD}, 0});
if (it != st.begin()) {
it--;
if (it->F.S == x - 1) {
upd(it->F.F, x - 1, id - it->S), l = it->F.F, st.erase(it);
}
}
st.insert({{l, r}, id});
}
void erase(int x, int id) {
auto it = st.upper_bound({{x, MOD}, 0});
it--;
int l =it->F.F, r = it->F.S;
upd(l, r, id - it->S); st.erase(it);
if (x > l) st.insert({{l, x - 1}, id});
if (x < r) st.insert({{x + 1, r}, id});
}
int main() {
scanf("%d%d\n%s", &n, &q, C + 1);
for (int i = 1; i <= n; i++) A[i] = C[i] - '0';
for (int i = 1; i <= n; i++) {
if (!A[i]) continue;
int j = i;
while (j <= n && A[j]) j++;
st.insert({{i, j - 1}, 0});
i = j;
}
tmp = st;
for (int i = 1; i <= q; i++) {
string t; cin >> t;
type[i] = (t == "toggle");
if (type[i]) {
scanf("%d", &ql[i]);
if (A[ql[i]]) {
__erase(ql[i]);
} else {
__add(ql[i]);
}
A[ql[i]] ^= 1;
} else {
scanf("%d%d", &ql[i], &qr[i]);
}
}
for (int i = 0; i < N; i++) {
vec[i].push_back(0);
sort(vec[i].begin(), vec[i].end());
vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
while (SZ(F[i]) < SZ(vec[i]) + 15) F[i].push_back(0);
}
st = tmp;
for (int i = 1; i <= n; i++) {
auto it = st.upper_bound({{i, MOD}, 0});
if (it != st.begin()) {
it--;
if (it->F.F <= i && it->F.S >= i) A[i] = 1;
else A[i] = 0;
}
}
for (int i = 1; i <= q; i++) {
if (type[i]) {
if (A[ql[i]]) erase(ql[i], i);
else add(ql[i], i);
A[ql[i]] ^= 1;
} else {
int x = get(ql[i], qr[i] - 1);
auto it = st.upper_bound({{ql[i], MOD}, 0});
if (it != st.begin()) {
it--;
if (it->F.S >= qr[i] - 1) x += i - it->S;
}
printf("%d\n", x);
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%d%d\n%s", &n, &q, C + 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d", &ql[i]);
| ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%d%d", &ql[i], &qr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
47340 KB |
Output is correct |
| 2 |
Correct |
118 ms |
47340 KB |
Output is correct |
| 3 |
Correct |
117 ms |
47340 KB |
Output is correct |
| 4 |
Correct |
117 ms |
47340 KB |
Output is correct |
| 5 |
Runtime error |
175 ms |
95852 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1093 ms |
90280 KB |
Output is correct |
| 2 |
Incorrect |
1196 ms |
88012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
96656 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
47340 KB |
Output is correct |
| 2 |
Runtime error |
184 ms |
96108 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
47340 KB |
Output is correct |
| 2 |
Correct |
118 ms |
47340 KB |
Output is correct |
| 3 |
Correct |
117 ms |
47340 KB |
Output is correct |
| 4 |
Correct |
117 ms |
47340 KB |
Output is correct |
| 5 |
Runtime error |
175 ms |
95852 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
