#include <bits/stdc++.h>
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
struct Segtree{
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;cin>>n>>q;
if(n>100||q>100){
return 0;
}
string str;cin>>str;
int b=-1;
set<pair<P,int>> st;
for(int i=0;i<n;i++){
if(str[i]=='1'){
if(b==-1){
b=i;
}
}else{
if(b!=-1){
st.insert(mp(P(b,i-1),-1));
b=-1;
}
}
}
if(b!=-1){
st.insert(mp(P(b,n-1),-1));
}
vector<pair<P,P>> v;
for(int i=0;i<q;i++){
string t;cin>>t;
if(t=="toggle"){
int a;cin>>a;--a;
auto add=[&](pair<P,int> p){
st.erase(p);
v.emplace_back(p.first,P(p.second,i));
};
if(str[a]=='0'){
str[a]='1';
pair<P,int> to=mp(P(a,a),i);
if(st.empty()){
st.insert(to);
continue;
}
auto ir=st.lower_bound(to);
auto il=ir;
if(ir!=st.end()&&(*ir).first.first==a+1){
to.first.second=(*ir).first.second;
add(*ir);
}
if(il!=st.begin()){
--il;
if((*il).first.second==a-1){
to.first.first=(*il).first.first;
add(*il);
}
}
st.insert(to);
}else{
str[a]='0';
auto it=st.lower_bound(mp(P(a+1,-1),-1));
--it;
pair<P,int> p=(*it);
add(*it);
if(p.first.first==p.first.second){
continue;
}
if(a==p.first.first){
st.insert(mp(P(p.first.first+1,p.first.second),i));
}else if(a==p.first.second){
st.insert(mp(P(p.first.first,p.first.second-1),i));
}else{
st.insert(mp(P(p.first.first,a-1),i));
st.insert(mp(P(a+1,p.first.second),i));
}
}
}else{
int a,b;cin>>a>>b;--a;--b;--b;
auto it=st.upper_bound(mp(P(a+1,-1),-1));
int res=0;
if(!st.empty()&&it!=st.begin()){
--it;
if((*it).first.first<=a&&b<=(*it).first.second){
//cout<<(*it).first.first<<" "<<(*it).first.second<<" "<<(*it).second<<" "<<i<<endl;
res+=i-(*it).second;
}
}
for(auto &e:v){
if(e.first.first<=a&&b<=e.first.second){
// cout<<e.second.first<<" "<<e.second.second<<endl;
res+=e.second.second-e.second.first;
}
}
cout<<res<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
