#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define N 300010
namespace seg{
ll dat[2*N];
void init(){
rep(i,2*N)dat[i]=0;
}
void add(ll i,ll x){
if(i<0)return;
i+=N;
for(;i;i>>=1)dat[i]+=x;
}
ll sum(ll l,ll r){
l+=N,r+=N+1;
ll res=0;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)res+=dat[a++];
if(b&1)res+=dat[--b];
}
return res;
}
}
typedef struct range{
ll l,r,val;
bool operator<(const range&key)const{
return this->l<key.r;
}
}range;
namespace DS{
set<range> S;
void init(){
seg::init();
S.clear();
}
void erase(set<range>::iterator it){
if(it==S.end())return;
seg::add(it->val,-(it->r-it->l+1));
S.erase(it);
}
void insert(ll l,ll r,ll val){
range x=(range){l,r,val};
while(1){
auto it=S.lower_bound(x);
if(it==S.end())break;
if(r<it->r)break;
erase(it);
}
auto it=S.lower_bound(x);
if(it!=S.end()){
if(r+1<=it->r){
seg::add(it->val,it->r-r);
S.insert((range){r+1,it->r,it->val});
}
erase(it);
}
it=S.lower_bound(x);
if(it!=S.begin()){
it--;
if(it->l<=l-1){
seg::add(it->val,l-it->l);
S.insert((range){it->l,l-1,it->val});
}
erase(it);
}
seg::add(val,r-l+1);
S.insert((range){l,r,val});
}
};
ll n,q;
string s;
vector<ll> upd[N];
typedef struct query{
ll a,b,id;
}query;
vector<query> qrys[N];
ll fans[N];
int main(){
cin>>n>>q;
cin>>s;
rep(i,n){
if(s[i]=='0')upd[i].push_back(0);
}
bool fi=1;
ll toggles=0;
ll rui[N];
for(int t=1;t<=q;t++){
string typ; cin>>typ;
if(typ=="toggle"){
ll x; cin>>x; x--;
if(s[x]=='0'){
upd[x].push_back(t);
s[x]='1';
}
else{
upd[x].push_back(t);
s[x]='0';
}
toggles=t;
}
if(typ=="query"){
if(fi){
rep(i,n)if(s[i]=='0')upd[i].push_back(t);
rui[0]=0;
for(int i=0;i<n;i++)rui[i+1]=rui[i]+(s[i]-'0');
fi=0;
}
ll a,b; cin>>a>>b; a--,b--;
fans[t]=(rui[b]-rui[a]==b-a)*(t-toggles-1);
//fans[t]=0;
qrys[b-1].push_back((query){a,b-1,t});
}
}
DS::init();
DS::S.insert((range){0,toggles,-1});
seg::add(-1,toggles+1);
for(int b=0;b<n;b++){
for(int i=0;i+1<upd[b].size();i+=2){
ll l=upd[b][i],r=upd[b][i+1]-1;
DS::insert(l,r,b);
//cerr<<"upd:"<<l<<" "<<r<<" "<<b<<endl;
}
for(query qry:qrys[b]){
//cerr<<"qry:"<<qry.a<<" "<<qry.b<<" "<<qry.id<<endl;
fans[qry.id]+=n-seg::sum(qry.a,qry.b);
}
}
for(int i=toggles+1;i<=q;i++){
cout<<fans[i]<<"\n";
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:130:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i+1<upd[b].size();i+=2){
~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
18936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
33144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
18936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
