| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1326556 | ee23b179_cp | Street Lamps (APIO19_street_lamps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
/*
- Maintain a set of maximal segments of contiguous ones.
- Whenever a segment is removed, create a point (a, b, -t).
- Whenever a segment is added, create a point (a, b, +t).
- Now for each query (aq, bq, tq), count the number of points (a, b, t)
such that a < aq , b > bq , t < tq
- Find the total sum of t, and the number of negative and positive events.
- If one positive event is missing, add 't' into the total sum.
- This can be easily solved with CDQ divide and conquer.
- My previous idea was using a 2D sparse segment tree to do the same,
but it uses too much memory. Alas, the remnants of my code were still there,
so i decided to reuse the 1D version instead of creating a new code for a
regular segment tree.
*/
using namespace std;
using ll = long long;
struct Node;
const int s1 = 2'000'000;
vector<Node> node(s1); int next1 = 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, int ct) {
if (v < xl || v > xr) return;
val.first += add;
val.second += ct;
if (xl != xr) {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!left) left = next1++;
node[left].update(v, xl, xm, add, ct);
} else {
if (!right) right = next1++;
node[right].update(v, xm+1, xr, add, ct);
}
}
}
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;
}
}
};
Node onTree, offTree;
vector<array<int,5>> updates;
vector<ll> offSum, onSum;
vector<int> offCount, onCount;
void cdq(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
cdq(l, m); cdq(m+1, r);
sort(updates.begin() + l, updates.begin() + m + 1,
[&](array<int,5> A, array<int,5> B) -> bool {
return A[1] < B[1];
});
sort(updates.begin() + m + 1, updates.begin() + r + 1,
[&](array<int,5> A, array<int,5> B) -> bool {
return A[1] < B[1];
});
stack<pair<int,int>> offActions, onActions;
int a = l, b = m+1;
while (a <= m || b <= r) {
bool isleft;
int cur;
if (a > m || (b <= r && updates[b][1] <= updates[a][1])) cur = b++, isleft = 0;
else cur = a++, isleft = 1;
if (updates[cur][3] == -1 && isleft) {
offTree.update(updates[cur][2], 0, n-1, updates[cur][0], +1);
offActions.push({updates[cur][2], updates[cur][0]});
} else if (updates[cur][3] == 1 && isleft) {
onTree.update(updates[cur][2], 0, n-1, updates[cur][0], +1);
onActions.push({updates[cur][2], updates[cur][0]});
} else if (updates[cur][3] == 0 && !isleft) {
int qi = updates[cur][4];
pair<ll,int> onDat = onTree.query(updates[cur][2]+1, n-1, 0, n-1);
onSum[qi] += onDat.first; onCount[qi] += onDat.second;
pair<ll,int> offDat = offTree.query(updates[cur][2]+1, n-1, 0, n-1);
offSum[qi] += offDat.first; offCount[qi] += offDat.second;
}
}
while (offActions.size()) {
offTree.update(offActions.top().first, 0, n-1, -offActions.top().second, -1);
offActions.pop();
}
while (onActions.size()) {
onTree.update(onActions.top().first, 0, n-1, -onActions.top().second, -1);
onActions.pop();
}
}
int main() {
int q;
cin >> n >> q;
string s;
cin >> s;
set<array<int,2>> segments;
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});
}
}
int qc = 0;
vector<int> qtime;
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;
updates.push_back({t, a, b-3, 0, qc++});
qtime.push_back(t);
}
}
sort(updates.begin(), updates.end());
offSum.resize(qc); onSum.resize(qc);
offCount.resize(qc); onCount.resize(qc);
cdq(0, (int) updates.size() - 1);
for (int i=0; i<qc; i++) {
ll ans = offSum[i] - onSum[i];
if (onCount[i] > offCount[i]) ans += qtime[i];
cout << ans << "\n";
}
return 0;
}