#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;
int fw[300005];
void update(int x, int v) {
for (; x<300005; x+=x&(-x)) fw[x] += v;
}
int sum(int x) {
int res = 0;
for(; x; x-=x&(-x)) res += fw[x];
return res;
}
int query(int x, int y){
return sum(y)-sum(x-1);
}
int n,q;
string s;
int ans[300005];
typedef pair<pii,pii>pi2;
vector<pi2>storage[300005];
vector<pi2>que[300005];
vector<pii>undo;
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;
vector<pi2>lque;
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}});
storage[mid+1].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){
storage[mid+1].push_back(it);
}
}
for(auto it:que[l]){
if(it.second.first<=mid){
lque.push_back(it);
}
else que[mid+1].push_back(it);
}
storage[l]=lstorage;
que[l]=lque;
lstorage.clear();
lque.clear();
dnc(l,mid);
dnc(mid+1,r);
vector<pi2>hold;
vector<pi2>hold2;
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){
int val=storage[l][cur].second.second-storage[l][cur].second.first+1;
update(storage[l][cur].first.second,val);
undo.push_back({storage[l][cur].first.second,-val});
cur++;
}
else{
break;
}
}
ans[index]+=query(rgt,n);
}
for(auto it:undo){
update(it.first,it.second);
}
undo.clear();
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].resize(0);
storage[mid+1].resize(0);
que[l].resize(0);
que[mid+1].resize(0);
storage[l]=hold;
que[l]=hold2;
hold.clear();
hold2.clear();
}
void solve(){
cin >> n >> q;
cin >> s;
s="0"+s+"0";
string temp;
int l,r;
int ptr=0;
set<pair<pii,int>>se;
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}});
}
se.clear();
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 |
4 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
4 ms |
15212 KB |
Output is correct |
| 5 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1913 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
39004 KB |
Output is correct |
| 2 |
Correct |
68 ms |
46040 KB |
Output is correct |
| 3 |
Correct |
56 ms |
37016 KB |
Output is correct |
| 4 |
Correct |
5 ms |
15284 KB |
Output is correct |
| 5 |
Runtime error |
1000 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
53932 KB |
Output is correct |
| 2 |
Correct |
83 ms |
55060 KB |
Output is correct |
| 3 |
Correct |
69 ms |
56164 KB |
Output is correct |
| 4 |
Correct |
56 ms |
53188 KB |
Output is correct |
| 5 |
Runtime error |
807 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
4 ms |
15212 KB |
Output is correct |
| 5 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 8 |
Runtime error |
1913 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
