#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;
int lazyUpd,lazySet;
bool lset;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0),lazySet(0),lset(0){
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void self_set(int x){
v=(e-s+1)*x;
lset=1;
lazySet=x;
lazyUpd=0;
}
void self_add(int x){
if(lset){
self_set(x+lazySet);
return;
}
v+=(e-s+1)*x;
lazyUpd+=x;
}
void forceProp(){
if(s==e) return;
if(lazyUpd){
l->self_add(lazyUpd),r->self_add(lazyUpd);
lazyUpd=0;
}
if(lset){
l->self_set(lazySet),r->self_set(lazySet);
lazySet=0;
lset=0;
}
}
void rangeUpd(int x, int y, int c){
if(x<=s&&y>=e){
self_add(c);
return;
}
forceProp();
if(x<=m)l->rangeUpd(x,y,c);
if(y>m)r->rangeUpd(x,y,c);
v=combine(l->v,r->v);
}
void rangeSet(int x, int y, int c){
if(x<=s&&y>=e){
self_set(c);
return;
}
forceProp();
if(x<=m)l->rangeSet(x,y,c);
if(y>m)r->rangeSet(x,y,c);
v=combine(l->v,r->v);
}
int query(int x, int y){
if(x<=s&&y>=e){
return v;
}
forceProp();
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));
}
};
int n,q;
string s;
node st(0,300005);
int ans[300005];
typedef pair<pii,pii>pi2;
vector<pi2>storage[300005];
vector<pi2>que[300005];
void dnc(int l, int r){
if(r<=l){
sort(storage[l].begin(),storage[l].end());
sort(que[l].begin(),que[l].end());
return;
}
vector<pi2>lstorage,rstorage;
vector<pi2>lque,rque;
int mid=(l+r)/2;
for(auto it:storage[l]){
if(it.second.first<=mid&&it.second.second>mid){
lstorage.push_back({it.first,{it.second.first,mid}});
rstorage.push_back({it.first,{mid+1,it.second.second}});
}
else if(it.second.second<=mid){
lstorage.push_back(it);
}
else if(it.second.first>mid){
rstorage.push_back(it);
}
}
for(auto it:que[l]){
if(it.second.first<=mid){
lque.push_back(it);
}
else rque.push_back(it);
}
storage[l]=lstorage;
storage[mid+1]=rstorage;
que[l]=lque;
que[mid+1]=rque;
dnc(l,mid);
dnc(mid+1,r);
vector<pi2>hold;
vector<pi2>hold2;
//cout << "storage[l]" << endl;
//for(auto it:storage[l]){
//cout << it.first.first <<" " << it.first.second << " " << it.second.first << " " << it.second.second << endl;
//}
//cout << "storage[mid+1]" << endl;
//for(auto it:storage[mid+1]){
//cout << it.first.first <<" " << it.first.second << " " << it.second.first << " " << it.second.second << endl;
//}
st.rangeSet(0,n+5,0);
int cur=0;
for(auto it:que[mid+1]){
int lft=it.first.first;
int rgt=it.first.second;
int index=it.second.second;
while(cur<(int)storage[l].size()){
if(storage[l][cur].first.first<=lft){
st.rangeUpd(storage[l][cur].first.second,storage[l][cur].first.second,storage[l][cur].second.second-storage[l][cur].second.first+1);
cur++;
}
else{
break;
}
}
ans[index]+=st.query(rgt,n);
}
merge(storage[l].begin(),storage[l].end(),storage[mid+1].begin(),storage[mid+1].end(),back_inserter(hold));
merge(que[l].begin(),que[l].end(),que[mid+1].begin(),que[mid+1].end(),back_inserter(hold2));
storage[l]=hold;
que[l]=hold2;
//cout << "merged" << endl;
//for(auto it:storage[l]){
//cout << it.first.first <<" " << it.first.second << " " << it.second.first << " " << it.second.second << endl;
//}
}
void solve(){
cin >> n >> q;
cin >> s;
s="0"+s+"0";
string temp;
int l,r;
int ptr=0;
//vector<pi2>que;
set<pair<pii,int>>se;
//vector<pi2>storage;
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(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[0].push_back({{hold.first.second,hold.first.first},{hold.second,x-1}});
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[0].push_back({{hold.first.second,hold.first.first},{hold.second,x-1}});
storage[0].push_back({{hold2.first.second,hold2.first.first},{hold2.second,x-1}});
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[0].push_back({{hold.first.second,hold.first.first},{hold.second,x-1}});
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[0].push_back({{hold.first.second,hold.first.first},{hold.second,x-1}});
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[0].push_back({{l,r},{x,ptr++}});
}
}
for(auto it:se){
storage[0].push_back({{it.first.second,it.first.first},{it.second,q}});
}
dnc(0,q);
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 |
Correct |
32 ms |
61776 KB |
Output is correct |
| 2 |
Correct |
31 ms |
61776 KB |
Output is correct |
| 3 |
Correct |
30 ms |
62168 KB |
Output is correct |
| 4 |
Correct |
30 ms |
62300 KB |
Output is correct |
| 5 |
Correct |
30 ms |
62300 KB |
Output is correct |
| 6 |
Correct |
29 ms |
61772 KB |
Output is correct |
| 7 |
Correct |
29 ms |
61776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1419 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
108556 KB |
Output is correct |
| 2 |
Correct |
126 ms |
111052 KB |
Output is correct |
| 3 |
Correct |
106 ms |
101648 KB |
Output is correct |
| 4 |
Correct |
32 ms |
62528 KB |
Output is correct |
| 5 |
Runtime error |
804 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
134396 KB |
Output is correct |
| 2 |
Correct |
147 ms |
136040 KB |
Output is correct |
| 3 |
Correct |
121 ms |
137008 KB |
Output is correct |
| 4 |
Correct |
101 ms |
133336 KB |
Output is correct |
| 5 |
Runtime error |
460 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
61776 KB |
Output is correct |
| 2 |
Correct |
31 ms |
61776 KB |
Output is correct |
| 3 |
Correct |
30 ms |
62168 KB |
Output is correct |
| 4 |
Correct |
30 ms |
62300 KB |
Output is correct |
| 5 |
Correct |
30 ms |
62300 KB |
Output is correct |
| 6 |
Correct |
29 ms |
61772 KB |
Output is correct |
| 7 |
Correct |
29 ms |
61776 KB |
Output is correct |
| 8 |
Runtime error |
1419 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
