oj.uz

Submission #729168

# Submission time Handle Problem Language Result Execution time Memory
729168 2023-04-23T15:10:21 Z 1075508020060209tc Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1025 ms 123404 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 672 ms 64660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9712 KB Output is correct
2 Correct 8 ms 9760 KB Output is correct
3 Correct 8 ms 9852 KB Output is correct
4 Correct 9 ms 9940 KB Output is correct
5 Correct 426 ms 27080 KB Output is correct
6 Correct 677 ms 51960 KB Output is correct
7 Correct 862 ms 76460 KB Output is correct
8 Correct 1025 ms 123404 KB Output is correct
9 Correct 548 ms 35008 KB Output is correct
10 Correct 634 ms 39444 KB Output is correct
11 Correct 603 ms 44680 KB Output is correct
12 Correct 933 ms 118844 KB Output is correct
13 Correct 979 ms 123380 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9940 KB Output is correct
2 Incorrect 9 ms 9852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -