#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node;
struct Node2;
const int s1 = 15'000'000;
const int s2 = 500'000;
vector<Node> node(s1); int next1 = 1;
vector<Node2> node2(s2); int next2 = 1;
int n;
struct Node {
int left, right;
pair<ll,int> val;
Node() : left(0), right(0), val({0,0}) {}
void update(int v, int xl, int xr, int add) {
if (v < xl || v > xr) return;
val.first += add;
val.second += 1;
if (xl != xr) {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!left) left = next1++;
node[left].update(v, xl, xm, add);
} else {
if (!right) right = next1++;
node[right].update(v, xm+1, xr, add);
}
}
}
pair<ll,int> query(int l, int r, int xl, int xr) {
if (l > r) return {0, 0};
if (l == xl && r == xr) {
return val;
} else {
pair<ll,int> ans = {0, 0};
int xm = (xl + xr) / 2;
if (left) {
pair<ll,int> leftans = node[left].query(l, min(r, xm), xl, xm);
ans.first += leftans.first;
ans.second += leftans.second;
}
if (right) {
pair<ll,int> rightans = node[right].query(max(l, xm+1), r, xm+1, xr);
ans.first += rightans.first;
ans.second += rightans.second;
}
return ans;
}
}
};
struct Node2 {
int left, right;
int val;
Node2() : left(0), right(0), val(0) {}
void update(int v, int w, int xl, int xr, int add) {
if (v < xl || v > xr) return;
if (!val) val = next1++;
node[val].update(w, 0, n-1, add);
if (xl != xr) {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!left) left = next2++;
node2[left].update(v, w, xl, xm, add);
} else {
if (!right) right = next2++;
node2[right].update(v, w, xm+1, xr, add);
}
}
}
pair<ll,int> query(int l1, int r1, int l2, int r2, int xl, int xr) {
if (l1 > r1) return {0, 0};
if (l1 == xl && r1 == xr) {
return node[val].query(l2, r2, 0, n-1);
} else {
pair<ll,int> ans = {0, 0};
int xm = (xl + xr) / 2;
if (left) {
pair<ll,int> leftans = node2[left].query(l1, min(r1, xm), l2, r2, xl, xm);
ans.first += leftans.first;
ans.second += leftans.second;
}
if (right) {
pair<ll,int> rightans = node2[right].query(max(l1, xm+1), r1, l2, r2, xm+1, xr);
ans.first += rightans.first;
ans.second += rightans.second;
}
return ans;
}
}
};
// lamp turns on => at most 2 segments destryod and 1 segment added
// lamp turns off => 1 segment destroyed and at most 2 segments added
// count number of x=<a ^ y>=b
// (t,a,b,1) => a and b were connected at t
// (t,a,b,-1) => a and b were disconnected at t
// now for each query, just need to find sum of t of a1<=a2, b2>=b1, t1<t2
// and if the number of '1' events is one less thaan the '-1' events,
// pretend there's (t2,a,b,-1)
// O(10^6) updates and O(5*10^5) queries, might not be fast enough.
int main() {
int q;
cin >> n >> q;
string s;
cin >> s;
set<array<int,2>> segments;
vector<array<int,3>> queries;
vector<array<int,4>> updates;
for (int i=0; i<n; i++) {
if (s[i] == '1') {
int l = i;
while (i < n-1 && s[i+1] == '1') i++;
segments.insert({l, i});
updates.push_back({0, l, i, +1});
}
}
for (int t=1; t<=q; t++) {
string type;
cin >> type;
if (type == "toggle") {
int i;
cin >> i;
i--;
if (s[i] == '0') {
int l = i, r = i;
auto right = segments.lower_bound({i, i});
if (right != segments.end() && right->at(0) == i+1) {
r = right->at(1);
updates.push_back({t, i+1, r, -1});
segments.erase(right);
}
auto left = segments.lower_bound({i, i});
if (left != segments.begin()) --left;
if (left != segments.end() && left->at(1) == i-1) {
l = left->at(0);
updates.push_back({t, l, i-1, -1});
segments.erase(left);
}
segments.insert({l, r});
updates.push_back({t, l, r, +1});
s[i] = '1';
} else {
auto it = prev(segments.lower_bound({i+1, i+1}));
int l = it->at(0), r = it->at(1);
segments.erase(it);
updates.push_back({t, l, r, -1});
if (l < i) {
segments.insert({l, i-1});
updates.push_back({t, l, i-1, +1});
}
if (r > i) {
segments.insert({i+1, r});
updates.push_back({t, i+1, r, +1});
}
s[i] = '0';
}
} else {
int a, b;
cin >> a >> b;
queries.push_back({t, a-1, b-2});
}
}
Node2 on, off;
for (array<int,4> upd : updates) {
if (upd[3] == -1) {
off.update(upd[1], upd[2], 0, n-1, upd[0]);
} else {
on.update(upd[1], upd[2], 0, n-1, upd[0]);
}
}
sort(queries.begin(), queries.end());
for (array<int,3> qur : queries) {
pair<ll,int> pOff = off.query(0, qur[1], qur[2], n-1, 0, n-1);
pair<ll,int> pOn = on.query(0, qur[1], qur[2], n-1, 0, n-1);
ll offSum = pOff.first;
ll onSum = pOn.first;
if (pOn.second > pOff.second) offSum += qur[0];
// cout << qur[0] << "," << qur[1] << "," << qur[2] << "\n";
// cout << pOff.first << "," << pOff.second << "\n";
// cout << pOn.first << "," << pOn.second << "\n";
// cout << offSum << "," << onSum << "\n";
cout << max(0LL, offSum - onSum) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
358308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
327 ms |
368604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
358484 KB |
Output is correct |
| 2 |
Correct |
58 ms |
358492 KB |
Output is correct |
| 3 |
Correct |
57 ms |
358484 KB |
Output is correct |
| 4 |
Correct |
55 ms |
358536 KB |
Output is correct |
| 5 |
Runtime error |
3103 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
358348 KB |
Output is correct |
| 2 |
Correct |
56 ms |
358544 KB |
Output is correct |
| 3 |
Correct |
56 ms |
358472 KB |
Output is correct |
| 4 |
Correct |
59 ms |
358668 KB |
Output is correct |
| 5 |
Correct |
559 ms |
371648 KB |
Output is correct |
| 6 |
Runtime error |
2841 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
358308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
