#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.l;
}
}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 ins(ll l,ll r,ll val){
if(l>r)return;
seg::add(val,r-l+1);
S.insert((range){l,r,val});
}
void insert(ll l,ll r,ll val){
//cerr<<"beg_sum:"<<seg::sum(0,N-1)<<endl;
range x=(range){l,r,val};
{//[l,r]に完全に含まれているものを消す
while(1){
auto it=S.lower_bound(x);
if(it==S.end())break;
if(r<it->r)break;
erase(it);
}
}
bool done=0;
{//[l,r]を完全に含んでいるものがある場合
auto it=S.upper_bound(x);
if(it!=S.begin()){
it--;
if(it->l<=l&&r<=it->r){
ll itl=it->l,itr=it->r,itval=it->val;
erase(it);
ins(itl,l-1,itval);
ins(r+1,itr,itval);
done=1;
ll sum=0;
for(auto e:S)sum+=e.r-e.l+1;
}
}
}
if(done==0){//そうでない場合
{//右側で交差しているもの
auto it=S.upper_bound(x);
if(it!=S.end()){
ll itl=it->l,itr=it->r,itval=it->val;
erase(it);
ins(r+1,itr,itval);
}
}
{//左側で交差しているもの
auto it=S.lower_bound(x);
if(it!=S.begin()){
it--;
ll itl=it->l,itr=it->r,itval=it->val;
erase(it);
ins(itl,l-1,itval);
}
}
}
//cerr<<"add:"<<l<<" "<<r<<" "<<val<<endl;
seg::add(val,r-l+1);
S.insert((range){l,r,val});
//cerr<<"seg_sum:"<<seg::sum(0,N-1)<<endl;
}
};
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;
//n=Data::n,q=Data::q;
cin>>s;
//s=Data::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;
//typ=Data::typ[t-1];
if(typ=="toggle"){
ll x;
cin>>x;
//x=Data::x[t-1];
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=Data::a[t-1],b=Data::b[t-1];
a--,b--;
fans[t]=(rui[b]-rui[a]==b-a)*(t-1-toggles);
qrys[b-1].push_back((query){a,b-1,t});
}
}
DS::init();
DS::ins(0,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]+=toggles+1-seg::sum(qry.a,qry.b);
}
}
for(int i=toggles+1;i<=q;i++){
cout<<fans[i]<<"\n";
//FANS.push_back(fans[i]);
}
}
Compilation message
street_lamps.cpp: In function 'void DS::insert(ll, ll, ll)':
street_lamps.cpp:89:9: warning: unused variable 'itl' [-Wunused-variable]
ll itl=it->l,itr=it->r,itval=it->val;
^~~
street_lamps.cpp:98:19: warning: unused variable 'itr' [-Wunused-variable]
ll itl=it->l,itr=it->r,itval=it->val;
^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:167: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 |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1359 ms |
28316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19192 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19192 KB |
Output is correct |
| 3 |
Correct |
17 ms |
19192 KB |
Output is correct |
| 4 |
Correct |
21 ms |
19192 KB |
Output is correct |
| 5 |
Correct |
674 ms |
45080 KB |
Output is correct |
| 6 |
Correct |
628 ms |
42120 KB |
Output is correct |
| 7 |
Correct |
594 ms |
38844 KB |
Output is correct |
| 8 |
Correct |
547 ms |
34756 KB |
Output is correct |
| 9 |
Correct |
901 ms |
29644 KB |
Output is correct |
| 10 |
Correct |
4807 ms |
25728 KB |
Output is correct |
| 11 |
Correct |
910 ms |
29408 KB |
Output is correct |
| 12 |
Execution timed out |
5035 ms |
25720 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
