#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
inline int combine(int a, int b){
return a+b;
}
struct node{
int s,e,m;
node *l,*r;
int v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, int y){
if(s==e){
v+=y;
return;
}
if(x<=m)l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
int query(int x, int y){
if(x<=s&&y>=e){
return v;
}
if(y<=m)return l->query(x,y);
if(x>m)return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
void solve(){
int n,q;
cin >> n >> q;
string s;
cin >> s;
s="0"+s+"0";
string temp;
int l,r;
vector<pair<pii,int>>que;
set<pair<pii,int>>se;
vector<pii>storage[n+5];
int ptr=0;
for(int x=1;x<=n;x++){
if(s[x]=='1'){
int cur=x;
for(int y=x;y<=n;y++){
if(s[y]=='0') break;
cur=y;
}
se.insert({{cur,x},0LL});
x=cur;
}
}
//for(auto it:se){
//show3(l,it.first.second,r,it.first.first,start,it.second);
//}
//show(se,1);
for(int x=1;x<=q;x++){
cin >> temp;
if(temp=="toggle"){
cin >> l;
if(s[l]=='1'){
//turn off
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold=*it;
storage[hold.first.second].push_back({hold.first.first,x-hold.second});
if(hold.first.second<l){
se.insert({{l-1,hold.first.second},x});
}
if(hold.first.first>l){
se.insert({{hold.first.first,l+1},x});
}
se.erase(se.find(hold));
s[l]='0';
}
else{
//turn on
if(s[l-1]=='1'&&s[l+1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold,hold2;
hold=*it;
it--;
hold2=*it;
storage[hold.first.second].push_back({hold.first.first,x-hold.second});
storage[hold2.first.second].push_back({hold2.first.first,x-hold2.second});
se.insert({{hold.first.first,hold2.first.second},x});
se.erase(se.find(hold));
se.erase(se.find(hold2));
}
else if(s[l-1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
it--;
pair<pii,int>hold=*it;
storage[hold.first.second].push_back({hold.first.first,x-hold.second});
se.insert({{l,hold.first.second},x});
se.erase(se.find(hold));
}
else if(s[l+1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold=*it;
storage[hold.first.second].push_back({hold.first.first,x-hold.second});
se.insert({{hold.first.first,l},x});
se.erase(se.find(hold));
}
else{
se.insert({{l,l},x});
}
s[l]='1';
}
}
else{
cin >> l >> r;
r--;
que.push_back({{l,r},ptr++});
}
//for(auto it:se){
//show3(l,it.first.second,r,it.first.first,start,it.second);
//}
//show(se,1);
}
for(auto it:se){
storage[it.first.second].push_back({it.first.first,q+1-it.second-ptr});
}
//for(int x=1;x<=n;x++){
//show(x,x);
//for(auto it:storage[x]){
//show2(r,it.first,val,it.second);
//}
//}
sort(que.begin(),que.end());
int ans[ptr];
node st(0,n+5);
int cur=1;
for(int x=0;x<ptr;x++){
int lft=que[x].first.first;
int rgt=que[x].first.second;
int index=que[x].second;
while(cur<=lft){
for(auto it:storage[cur]){
st.upd(it.first,it.second);
}
cur++;
}
ans[index]=st.query(rgt,n);
}
for(int x=0;x<ptr;x++){
cout << ans[x] << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
13308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
