/*
- 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 (we don't take credit of equal elements because the given input is one-based)
- 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.
*/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int MX = 3e5 + 5;
pii operator +(const pii &a, const pii &b){
return {a.fi + b.fi, a.se + b.se};
}
pii operator -(const pii &a, const pii &b){
return {a.fi - b.fi, a.se - b.se};
}
struct BIT{
vector<pii> bit;
BIT(int n) : bit(n + 1) {}
inline void add(int idx, pii val){
for(++idx; idx < sz(bit); idx += idx & -idx){
bit[idx] = bit[idx] + val;
}
return;
}
inline pii query(int idx){
pii ret = {0, 0};
for(++idx; idx; idx -= idx & -idx){
ret = ret + bit[idx];
}
return ret;
}
inline pii query(int l, int r){
return query(r) - query(l - 1);
}
};
vector<array<int, 5>> updates;
vector<pii> onans, offans;
BIT on(MX), off(MX);
inline void cdq(int l, int r){
if(l + 1 == r) return;
int m = (l + r) / 2;
cdq(l, m); cdq(m, r);
vector<pair<int, pii>> offrec, onrec;
vector<array<int, 5>> temp;
int a = l, b = m;
while(a < m || b < r){
bool left;
int cur;
if(a >= m || (b < r && updates[b][1] <= updates[a][1])) cur = b++, left = false;
else cur = a++, left = true;
temp.emplace_back(updates[cur]);
if(left && updates[cur][3] == -1){
off.add(updates[cur][2], {updates[cur][0], 1});
offrec.push_back({updates[cur][2], {-updates[cur][0], -1}});
}
else if(left && updates[cur][3] == 1){
on.add(updates[cur][2], {updates[cur][0], 1});
onrec.push_back({updates[cur][2], {-updates[cur][0], -1}});
}
else if(!left && !updates[cur][3]){
pii onval = on.query(updates[cur][2] + 1, MX - 1), offval = off.query(updates[cur][2] + 1, MX - 1);
onans[updates[cur][4]] = onans[updates[cur][4]] + onval, offans[updates[cur][4]] = offans[updates[cur][4]] + offval;
}
}
for(int i = 0; i < sz(offrec); i++){
off.add(offrec[i].fi, offrec[i].se);
}
for(int i = 0; i < sz(onrec); i++){
on.add(onrec[i].fi, onrec[i].se);
}
for(int i = l; i < r; i++){
updates[i] = temp[i - l];
}
temp.clear(), offrec.clear(), onrec.clear();
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q;
string s, type;
cin >> n >> q >> s;
set<pii> seg;
for(int i = 0; i < n; i++){
if(s[i] == '1'){
int l = i;
while(i + 1 < n && s[i + 1] == '1') i++;
seg.emplace(l, i);
updates.push_back({0, l, i, 1});
}
}
int qc = 0;
vi qtime;
for(int t = 1; t <= q; t++){
cin >> type;
if(type == "toggle"){
int i;
cin >> i;
if(s[--i] == '0'){
int l = i, r = i;
auto right = seg.lower_bound({i, i});
if(right != seg.end() && right->fi == i + 1){
r = right->se;
updates.push_back({t, i + 1, r, -1});
seg.erase(right);
}
auto left = seg.lower_bound({i, i});
if(left != seg.begin()) left--;
if(left != seg.end() && left->se == i - 1){
l = left->fi;
updates.push_back({t, l, i - 1, -1});
seg.erase(left);
}
seg.emplace(l, r);
updates.push_back({t, l, r, 1});
s[i] = '1';
}
else{
auto it = prev(seg.lower_bound({i + 1, i + 1}));
int l = it->fi, r = it->se;
updates.push_back({t, l, r, -1});
if(l < i){
updates.push_back({t, l, i - 1, 1});
seg.emplace(l, i - 1);
}
if(r > i){
updates.push_back({t, i + 1, r, 1});
seg.emplace(i + 1, r);
}
s[i] = '0';
}
}
else{
int ql, qr;
cin >> ql >> qr;
updates.push_back({t, ql, qr - 3, 0, qc++}); // qr - 3 ?
qtime.emplace_back(t);
}
}
sort(updates.begin(), updates.end());
onans.resize(qc), offans.resize(qc);
cdq(0, sz(updates));
for(int i = 0; i < qc; i++){
int ans = offans[i].fi - onans[i].fi;
if(onans[i].se > offans[i].se) ans += qtime[i];
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
556 ms |
72832 KB |
Output is correct |
| 2 |
Incorrect |
554 ms |
73216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10064 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10064 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10064 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9808 KB |
Output is correct |
| 5 |
Correct |
863 ms |
106808 KB |
Output is correct |
| 6 |
Correct |
904 ms |
115696 KB |
Output is correct |
| 7 |
Correct |
766 ms |
112448 KB |
Output is correct |
| 8 |
Correct |
434 ms |
74484 KB |
Output is correct |
| 9 |
Correct |
175 ms |
53448 KB |
Output is correct |
| 10 |
Correct |
229 ms |
70592 KB |
Output is correct |
| 11 |
Correct |
231 ms |
70592 KB |
Output is correct |
| 12 |
Correct |
408 ms |
74488 KB |
Output is correct |
| 13 |
Correct |
437 ms |
74640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10064 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
