Submission #729168

#	Time	Username	Problem	Language	Result	Execution time	Memory
729168		1075508020060209tc	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	1025 ms	123404 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;
#define int long long
int lowbit(int x){return x&-x;}

int bit[300005];
void upd(int pl,int val){
while(pl<=300000){
    bit[pl]+=val;
    pl+=lowbit(pl);
}
}
int qsum(int l,int r){
int ret=0;
while(r){
    ret+=bit[r];
    r-=lowbit(r);
}
l--;
while(l){
    ret-=bit[l];
    l-=lowbit(l);
}
return ret;
}



int n;int Q;

string tss;

int ar[300005];
string typ[300005];int qa[300005];int qb[300005];
int ps[300005];
int ans[300005];

void build(int l,int r){
for(int i=l;i<=r;i++){
    if(typ[i]=="toggle"){
        upd(qa[i],1);
    }
}
}
void undo(int l,int r){
for(int i=l;i<=r;i++){
    if(typ[i]=="toggle"){
        upd(qa[i],-1);
    }
}
}

void split(vector<int>&lv,vector<int>&rv,vector<int>v){
for(int i=0;i<v.size();i++){
    int id=v[i];
    int a=qa[id];int b=qb[id];
    b--;
    int len=b-a+1;
    if(qsum(a,b)==len){
        lv.push_back(id);
    }else{
        rv.push_back(id);
    }
}
}

void totalbs(vector<int>qid,int l,int r){
//cout<<l<<" "<<r<<endl;
if(l==r){
    for(int i=0;i<qid.size();i++){
        ans[qid[i]]=l;
    }
return;
}

int mi=(l+r)/2;
build(l,mi);
vector<int>lv;vector<int>rv;
split(lv,rv,qid);
totalbs(rv,mi+1,r);
undo(l,mi);
totalbs(lv,l,mi);
return;
}


signed main(){
cin>>n>>Q;
cin>>tss;tss="*"+tss;
for(int i=1;i<=n;i++){
    ar[i]=tss[i]-'0';
}
vector<int>qid;

for(int i=1;i<=Q;i++){
    cin>>typ[i];
    if(typ[i][0]=='q'){
        qid.push_back(i);
        cin>>qa[i]>>qb[i];
    }else{
        cin>>qa[i];
    }
}

for(int i=1;i<=n;i++){
    upd(i,ar[i]);
}

totalbs(qid,0,Q+1);


for(int i=1;i<=Q;i++){
    if(typ[i][0]=='q'){
        cout<<max(0ll,i-ans[i])<<endl;
    }
}



}

Compilation message (stderr)

street_lamps.cpp: In function 'void split(std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>)':
street_lamps.cpp:56:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 | for(int i=0;i<v.size();i++){
      |             ~^~~~~~~~~
street_lamps.cpp: In function 'void totalbs(std::vector<long long int>, long long int, long long int)':
street_lamps.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<qid.size();i++){
      |                 ~^~~~~~~~~~~

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