#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
struct node {
int pref, suf;
vector<pair<int, int>> left_events;
vector<pair<int, int>> right_events;
vector<pair<int, pair<int, int>>> queries;
};
const int inf = 1e9 + 20;
const int maxN = 3e5 + 20;
int a[maxN];
int res[maxN];
node tr[maxN * 4];
int sum_single[maxN];
int prv_single[maxN];
void add_event(int id, int T) {
if (tr[id].left_events.empty() || tr[id * 2].suf != tr[id].left_events.back().second) {
tr[id].left_events.push_back({T, tr[id * 2].suf});
}
if (tr[id].right_events.empty() || tr[id * 2 + 1].pref != tr[id].right_events.back().second) {
tr[id].right_events.push_back({T, tr[id * 2 + 1].pref});
}
}
void merge(int id, int lt, int rt, int mt, int T) {
tr[id].pref = tr[id * 2].pref + (tr[id * 2].pref == mt - lt + 1 ? tr[id * 2 + 1].pref : 0);
tr[id].suf = tr[id * 2 + 1].suf + (tr[id * 2 + 1].suf == rt - mt ? tr[id * 2].suf : 0);
add_event(id, T);
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tr[id].pref = a[lt];
tr[id].suf = a[lt];
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
merge(id, lt, rt, mt, 0);
}
void update(int id, int lt, int rt, int pos, int T) {
if (lt == rt) {
if (a[lt] == 1) {
sum_single[lt] += T - prv_single[lt];
}
prv_single[lt] = T;
a[lt] ^= 1;
tr[id].pref = a[lt];
tr[id].suf = a[lt];
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(id * 2, lt, mt, pos, T);
}
else {
update(id * 2 + 1, mt + 1, rt, pos, T);
}
merge(id, lt, rt, mt, T);
}
void add(int id, int lt, int rt, int ql, int qr, int T) {
if (lt == rt) {
res[T] = sum_single[lt];
if (a[lt] == 1) {
res[T] += T - prv_single[lt];
}
return;
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
add(id * 2, lt, mt, ql, qr, T);
}
else if (ql >= mt + 1) {
add(id * 2 + 1, mt + 1, rt, ql, qr, T);
}
else {
tr[id].queries.push_back({T, {mt - ql + 1, qr - mt}});
}
}
void solve(int id) {
vector<pair<int, pair<int, int>>> &queries = tr[id].queries;
vector<pair<int, int>> &left_events = tr[id].left_events;
vector<pair<int, int>> &right_events = tr[id].right_events;
if (queries.empty()) {
return;
}
left_events.push_back({inf, -1});
right_events.push_back({inf, -1});
vector<pair<int, pair<int, int>>> events;
int sz_left = left_events.size();
int sz_right = right_events.size();
int sz_queries = queries.size();
vector<int> left_pos(sz_left);
vector<int> right_pos(sz_right);
vector<int> query_pos(sz_queries);
for (int i = 0; i < sz_left; i++) {
events.push_back({left_events[i].first, {0, i}});
}
for (int i = 0; i < sz_right; i++) {
events.push_back({right_events[i].first, {1, i}});
}
for (int i = 0; i < sz_queries; i++) {
events.push_back({queries[i].first, {2, i}});
}
sort(events.begin(), events.end());
int n = 0;
vector<int> len;
for (int i = 0; i < (int)events.size(); i++) {
if (i > 0 && events[i].first != events[i - 1].first) {
len.push_back(events[i].first - events[i - 1].first);
n++;
}
if (events[i].second.first == 0) {
left_pos[events[i].second.second] = n;
}
if (events[i].second.first == 1) {
right_pos[events[i].second.second] = n;
}
if (events[i].second.first == 2) {
query_pos[events[i].second.second] = n - 1;
}
}
vector<int> left_val(n);
vector<int> right_val(n);
for (int i = 0; i < sz_left - 1; i++) {
for (int j = left_pos[i]; j < left_pos[i + 1]; j++) {
left_val[j] = left_events[i].second;
}
}
for (int i = 0; i < sz_right - 1; i++) {
for (int j = right_pos[i]; j < right_pos[i + 1]; j++) {
right_val[j] = right_events[i].second;
}
}
for (int id = 0; id < sz_queries; id++) {
int T = queries[id].first;
int X = queries[id].second.first;
int Y = queries[id].second.second;
res[T] = 0;
for (int i = 0; i <= query_pos[id]; i++) {
if (left_val[i] >= X && right_val[i] >= Y) {
res[T] += len[i];
}
}
}
}
void solve(int id, int lt, int rt) {
if (lt == rt) {
return;
}
solve(id);
int mt = (lt + rt) / 2;
solve(id * 2, lt, mt);
solve(id * 2 + 1, mt + 1, rt);
}
void just_do_it() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
a[i] = c - '0';
}
build(1, 1, n);
for (int T = 1; T <= q; T++) {
res[T] = -1;
string s;
cin >> s;
if (s == "toggle") {
int pos;
cin >> pos;
update(1, 1, n, pos, T);
}
if (s == "query") {
int ql, qr;
cin >> ql >> qr;
qr--;
add(1, 1, n, ql, qr, T);
}
}
solve(1, 1, n);
for (int i = 1; i <= q; i++) {
if (res[i] != -1) {
cout << res[i] << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94140 KB |
Output is correct |
2 |
Correct |
48 ms |
94144 KB |
Output is correct |
3 |
Correct |
58 ms |
94152 KB |
Output is correct |
4 |
Correct |
62 ms |
94236 KB |
Output is correct |
5 |
Correct |
59 ms |
94156 KB |
Output is correct |
6 |
Correct |
60 ms |
94240 KB |
Output is correct |
7 |
Correct |
62 ms |
94252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
101196 KB |
Output is correct |
2 |
Correct |
169 ms |
100976 KB |
Output is correct |
3 |
Correct |
168 ms |
101760 KB |
Output is correct |
4 |
Correct |
402 ms |
122300 KB |
Output is correct |
5 |
Correct |
418 ms |
121428 KB |
Output is correct |
6 |
Correct |
422 ms |
123376 KB |
Output is correct |
7 |
Correct |
221 ms |
115984 KB |
Output is correct |
8 |
Correct |
240 ms |
117268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94320 KB |
Output is correct |
2 |
Correct |
42 ms |
94376 KB |
Output is correct |
3 |
Correct |
44 ms |
94372 KB |
Output is correct |
4 |
Correct |
44 ms |
94368 KB |
Output is correct |
5 |
Correct |
535 ms |
124680 KB |
Output is correct |
6 |
Correct |
1292 ms |
125180 KB |
Output is correct |
7 |
Correct |
3493 ms |
125484 KB |
Output is correct |
8 |
Execution timed out |
5041 ms |
125176 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
94348 KB |
Output is correct |
2 |
Correct |
43 ms |
94352 KB |
Output is correct |
3 |
Correct |
44 ms |
94288 KB |
Output is correct |
4 |
Correct |
44 ms |
94284 KB |
Output is correct |
5 |
Execution timed out |
5069 ms |
127008 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94140 KB |
Output is correct |
2 |
Correct |
48 ms |
94144 KB |
Output is correct |
3 |
Correct |
58 ms |
94152 KB |
Output is correct |
4 |
Correct |
62 ms |
94236 KB |
Output is correct |
5 |
Correct |
59 ms |
94156 KB |
Output is correct |
6 |
Correct |
60 ms |
94240 KB |
Output is correct |
7 |
Correct |
62 ms |
94252 KB |
Output is correct |
8 |
Correct |
156 ms |
101196 KB |
Output is correct |
9 |
Correct |
169 ms |
100976 KB |
Output is correct |
10 |
Correct |
168 ms |
101760 KB |
Output is correct |
11 |
Correct |
402 ms |
122300 KB |
Output is correct |
12 |
Correct |
418 ms |
121428 KB |
Output is correct |
13 |
Correct |
422 ms |
123376 KB |
Output is correct |
14 |
Correct |
221 ms |
115984 KB |
Output is correct |
15 |
Correct |
240 ms |
117268 KB |
Output is correct |
16 |
Correct |
43 ms |
94320 KB |
Output is correct |
17 |
Correct |
42 ms |
94376 KB |
Output is correct |
18 |
Correct |
44 ms |
94372 KB |
Output is correct |
19 |
Correct |
44 ms |
94368 KB |
Output is correct |
20 |
Correct |
535 ms |
124680 KB |
Output is correct |
21 |
Correct |
1292 ms |
125180 KB |
Output is correct |
22 |
Correct |
3493 ms |
125484 KB |
Output is correct |
23 |
Execution timed out |
5041 ms |
125176 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |