#include<bits/stdc++.h>
using namespace std;
const int nax = 3e5 + 2;
const int qax = 3e5 + 2;
const int INF = 1e9;
struct BIT {
vector<int>fen;
int N;
BIT(int sz) {
fen.assign(sz+10, 0);
N = sz;
}
void add(int pos, int val) {
assert(pos>0);
while(pos<=N) {
fen[pos] += val;
pos += (pos&-pos);
}
}
int get(int pos) {
int sum = 0;
while(pos>0) {
sum += fen[pos];
//cerr<<pos<<' '<<sum<<endl;
pos -= (pos&-pos);
}
return sum;
}
int get(int l, int r) {
int sum = get(r);
if(l>1) sum -= get(l-1);
return sum;
}
};
void PlayGround() {
int n, q;
cin>>n>>q;
string s;
cin>>s;
s = '@' + s;
int prv = 0;
int ans[q+1];
memset(ans, -1, sizeof ans);
set<array<int, 3>>st; // l, r, index
vector<array<int, 5>>bag; // l, t0, t1, r, index
s += '0';
for(int i=1; i<=n+1; ++i) {
if(s[i]=='0') {
if(prv!=i-1) {
st.insert({prv+1, i-1, (int)bag.size()});
bag.push_back({prv+1, 1, q, i-1, -1});
}
prv = i;
}
}
s.pop_back();
for(int i=1; i<=q; ++i) {
string type;
cin>>type;
if(type=="toggle") {
int j;
cin>>j;
if(s[j]=='0') {
s[j] = '1';
auto it = st.lower_bound({j, 0, 0});
//cerr<<(*it)[0]<<' '<<(*it)[1]<<endl;
if(it!=st.end() && (*it)[0]==j+1 && it!=st.begin() && (*prev(it))[1]==j-1) {
auto x = prev(it), y = it;
st.erase(x), st.erase(y);
bag[(*x)[2]][2] = i;
bag[(*y)[2]][2] = i;
st.insert({(*x)[0], (*y)[1], (int)bag.size()});
bag.push_back({(*x)[0], i+1, q, (*y)[1], -1});
} else if(it!=st.end() && (*it)[0]==j+1) {
auto x = it;
st.erase(x);
bag[(*x)[2]][2] = i;
st.insert({j, (*x)[1], (int)bag.size()});
bag.push_back({j, i+1, q, (*x)[1], -1});
} else if(it!=st.begin() && (*prev(it))[1]==j-1) {
auto x = it;
st.erase(x);
bag[(*x)[2]][2] = i;
st.insert({(*x)[0], j, (int)bag.size()});
bag.push_back({(*x)[0], i+1, q, j, -1});
} else {
st.insert({j, j, (int)bag.size()});
bag.push_back({j, i+1, q, j, -1});
}
} else {
s[j] = '0';
auto it = st.lower_bound({j, 0, 0});
if(it==st.end() || (*it)[0]!=j) it = prev(it);
st.erase(it);
bag[(*it)[2]][2] = i;
if((*it)[1]==(*it)[0]) {
} else if(j==(*it)[0]) {
st.insert({j+1, (*it)[1], (int)bag.size()});
bag.push_back({j+1, i+1, q, (*it)[1], -1});
} else if(j==(*it)[1]) {
st.insert({(*it)[0], j-1, (int)bag.size()});
bag.push_back({(*it)[0], i+1, q, j-1, -1});
} else {
st.insert({(*it)[0], j-1, (int)bag.size()});
bag.push_back({(*it)[0], i+1, q, j-1, -1});
st.insert({j+1, (*it)[1], (int)bag.size()});
bag.push_back({j+1, i+1, q, (*it)[1], -1});
}
}
} else {
int a, b;
cin>>a>>b;
--b;
bag.push_back({a, INF, INF, b, i});
}
}
BIT b1(nax), b2(qax), b3(qax);
sort(bag.begin(), bag.end());
// for(auto x : bag) {
// cerr<<x[0]<<' '<<x[1]<<' '<<x[2]<<' '<<x[3]<<' '<<x[4]<<endl;
// }
for(auto x : bag) {
//cerr<<x[4]<<endl;
if(x[4]!=-1) {
ans[x[4]] = b1.get(x[3], nax);
ans[x[4]] -= b2.get(x[4], qax);
ans[x[4]] += b3.get(x[4], qax) * x[4];
} else {
b1.add(x[3], x[2]-x[1]+1);
b2.add(x[2], x[2]);
b3.add(x[2], 1);
}
}
for(int i=1; i<=q; ++i) if(ans[i]!=-1) {
cout<<ans[i]<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2900 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
