Submission #731823

#	Time	Username	Problem	Language	Result	Execution time	Memory
731823		1075508020060209tc	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2834 ms	288548 KiB

street_lamps

//#include "lib2249.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long

int lowbit(int x){return x&-x;}
int bit[500005];
void upd(int pl,int val){
while(pl<=500000){
    bit[pl]+=val;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
//if(pl<0){return 0;}
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}



int n;int Q;
string ts;
int ar[500005];
string typs[500005];
int ans[500005];
set<pair<int,int>>seg;


struct cdq{
int t;int x;int y;
int val;int id;
};
bool cmp(cdq i,cdq j){
if(i.t<j.t){return 1;}
return 0;
if(i.t>j.t){return 0;}
if(i.x>j.x){return 1;}
return 0;
}


vector<cdq>pts;

void ptins(int a,int b,int c,int d,int vl,int t){
pts.push_back({t,c,d,vl,0});
pts.push_back({t,a-1,b-1,vl,0});
pts.push_back({t,c,b-1,-vl,0});
pts.push_back({t,a-1,d,-vl,0});
}
vector<cdq>tpts;

void mrg(int a,int b,int vl,int t){
auto rit=seg.upper_bound({a,9999999});
auto lit=prev(rit);
int ll=(*lit).first;int lr=(*lit).second;
int rl=(*rit).first;int rr=(*rit).second;

//cout<<"mrg"<<a<<" "<<b<<" "<<vl<<" "<<t<<":  ";
//cout<<ll<<" "<<lr<<" "<<rl<<" "<<rr<<endl;
ptins(ll,rl,lr,rr,vl,t);
seg.erase(rit);
seg.erase(lit);
seg.insert({ll,rr});
}



void solve(int L,int R){

if(L==R){return;}
int md=(L+R)/2;
solve(L,md);solve(md+1,R);
//cout<<L<<" "<<R<<endl;

int lit=L;int rit=md+1;

for(int it=L;it<=R;it++){
    if(rit==R+1||(lit<=md&&pts[lit].x>=pts[rit].x)){
        if(pts[lit].id==0){
            upd(pts[lit].y,pts[lit].val);
        }
        tpts[it]=pts[lit];
        lit++;
    }else{
        if(pts[rit].id!=0){
            ans[pts[rit].id]+=qsum(500000)-qsum(pts[rit].y-1);
        }
        tpts[it]=pts[rit];
        rit++;
    }
}



for(int i=L;i<=md;i++){
    if(pts[i].id==0){
        upd(pts[i].y,-pts[i].val);
    }
}
for(int i=L;i<=R;i++){
    pts[i]=tpts[i];
}
}


void violence(){


for(int i=1;i<pts.size();i++){
    if(pts[i].id==0){continue;}
    for(int j=1;j<pts.size();j++){
        if(pts[j].id){continue;}
        if(pts[j].t<pts[i].t&&pts[j].x>=pts[i].x&&pts[j].y>=pts[i].y){
            ans[pts[i].id]+=pts[j].val;
        }
    }
}


}



signed main(){




cin>>n>>Q;
cin>>ts;
for(int i=1;i<=n;i++){
    ar[i]=ts[i-1]-'0';
    upd(i,ar[i]);
    if(ar[i]){
        ptins(i,i,i,i,Q+1,0);
    }
}
for(int i=1;i<=n;i++){
    if(ar[i]==0){continue;}
    int l=i;
    seg.insert({i,i});
    while(i+1<=n&&ar[i+1]==1){
        seg.insert({i+1,i+1});
        mrg(i,i+1,Q+1,0);
        i++;
    }
}
/*
for(auto it=seg.begin();it!=seg.end();it++){
    cout<<(*it).first<<" "<<(*it).second<<endl;
}
*/

for(int i=1;i<=Q;i++){
    cin>>typs[i];
    if(typs[i]=="toggle"){
    int pl;
    cin>>pl;
    ar[pl]^=1;
    if(ar[pl]==1){
        upd(pl,1);
        seg.insert({pl,pl});
        if(pl>=2&&ar[pl-1]==1){
            mrg(pl-1,pl,Q+1-i,i);
        }
        if(pl<=n-1&&ar[pl+1]==1){
            mrg(pl,pl+1,Q+1-i,i);
        }
        ptins(pl,pl,pl,pl,(Q+1-i),i);
    }else{
        upd(pl,-1);
        auto it=seg.upper_bound({pl,9999999});
        it=prev(it);
        int l=(*it).first;int r=(*it).second;
        seg.erase(it);
        if(l<pl){
            ptins(l,pl,pl-1,r,-(Q+1-i),i);
        }
        if(r>pl){
            ptins(pl,pl+1,pl,r,-(Q+1-i),i);
        }
        if(r>pl){
            seg.insert({pl+1,r});
        }
        if(l<pl){
            seg.insert({l,pl-1});
        }
        ptins(pl,pl,pl,pl,-(Q+1-i),i);
    }

    }else{
        int a;int b;
        cin>>a>>b;
        b--;

        if((qsum(b)-qsum(a-1))==(b-a+1) ){
            ans[i]-=Q+1-i;
            //cout<<i<<" "<<ans[i]<<"hihi\n";
        }
        pts.push_back({i,a,b,0,i});
    }
}

pts.insert(pts.begin()+0,{0,0,0,0,0});
sort(pts.begin()+1,pts.end(),cmp);

tpts.resize(pts.size()+10);
/*
for(int i=1;i<pts.size();i++){
    cout<<pts[i].t<<" "<<pts[i].x<<" "<<pts[i].y<<" "<<pts[i].val<<" "<<pts[i].id<<endl;
}*/

/*
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<"__\n";
}
*/

for(int i=0;i<=500000;i++){
    bit[i]=0;
}

for(int i=0;i<pts.size();i++){
    pts[i].y+=10;
}







solve(1,pts.size()-1);
//violence();






for(int i=1;i<=Q;i++){
    if(typs[i]!="toggle"){
        cout<<ans[i]<<endl;
    }
}


}


/*
void op(set<int>st){

for(auto it=st.begin();it!=st.end();it++){
    cout<<*it<<" ";
}cout<<endl;

}
*/

Compilation message (stderr)

street_lamps.cpp: In function 'void violence()':
street_lamps.cpp:114:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cdq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 | for(int i=1;i<pts.size();i++){
      |             ~^~~~~~~~~~~
street_lamps.cpp:116:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cdq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int j=1;j<pts.size();j++){
      |                 ~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:145:9: warning: unused variable 'l' [-Wunused-variable]
  145 |     int l=i;
      |         ^
street_lamps.cpp:228:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cdq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 | for(int i=0;i<pts.size();i++){
      |             ~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20