#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 3e5 + 100;
ll fen[MAXN], t = 0;
set<pair<int,pair<int,int>>> st;
set<int> zeros;
vector<int> A;
void add(int k, int val) {
while (k < MAXN) {
fen[k] += val;
k += k & -k;
}
}
int get(int k) {
ll res = 0;
while (k > 0) {
res += fen[k];
k -= k & -k;
}
return res;
}
void close_int(int l, int r, int open_time, int close_time) {
st.erase({l, {0, open_time}});
st.erase({r, {1, open_time}});
add(l, close_time - open_time);
add(r, - close_time + open_time);
}
void open_int(int l, int r, int t) {
st.insert({l, {0, t}});
st.insert({r, {1, t}});
}
int main() {
fast
int n, q;
cin >> n >> q;
A = vector<int>(n+2, 0);
string s;
cin >> s;
for (int i = 1; i <= n; i++) {
A[i] = s[i-1] - '0';
if (A[i] == 0)
zeros.insert(i);
}
for (int i = 1; i <= n; i++) {
if (A[i-1] == 0 && A[i])
st.insert({i, {0, 0}});
if (A[i] && (i == n || A[i+1] == 0))
st.insert({i, {1, 0}});
}
while (q--) {
t++;
string type;
cin >> type;
if (type == "toggle") {
int x;
cin >> x;
if (A[x]) {
auto u = st.lower_bound({x, {1, 0}});
auto v = prev(u);
int l = (*v).f, r = (*u).f, last_time = (*v).s.s;
close_int(l, r, last_time, t-1);
if (l <= x - 1)
open_int(l, x-1, t);
if (x + 1 <= r)
open_int(x+1, r, t);
} else {
if (A[x-1] && A[x+1]) {
auto u_left = st.lower_bound({x-1, {1, 0}});
auto v_left = prev(u_left);
auto u_right = st.lower_bound({x+1, {1, 0}});
auto v_right = prev(u_right);
close_int((*v_left).f, (*u_left).f, (*u_left).s.s, t-1);
close_int((*v_right).f, (*u_right).f, (*u_right).s.s, t-1);
open_int((*v_left).f, (*u_right).f, t);
} else if (A[x-1]) {
auto u_left = st.lower_bound({x-1, {1, 0}});
auto v_left = prev(u_left);
close_int((*v_left).f, (*u_left).f, (*u_left).s.s, t-1);
open_int((*v_left).f, x, t);
} else if (A[x+1]) {
auto u_right = st.lower_bound({x+1, {1, 0}});
auto v_right = prev(u_right);
close_int((*v_right).f, (*u_right).f, (*u_right).s.s, t-1);
open_int(x, (*u_right).f, t);
} else
open_int(x, x, t);
}
if (A[x] == 0)
zeros.erase(x);
else
zeros.insert(x);
A[x] ^= 1;
} else {
int l, r;
cin >> l >> r;
r--;
ll ans = get(r);
if (zeros.lower_bound(l) == zeros.end() || *zeros.lower_bound(l) > r) {
auto u = st.lower_bound({l, {1, 0}});
auto v = prev(u);
ans += t - (*u).s.s;
}
cout << ans << "\n";
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:127:22: warning: variable 'v' set but not used [-Wunused-but-set-variable]
127 | auto v = prev(u);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
