oj.uz

Submission #731823

# Submission time Handle Problem Language Result Execution time Memory
731823 2023-04-28T04:00:26 Z 1075508020060209tc Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2834 ms 288548 KB 
//#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 11 ms 19924 KB Output is correct
3 Correct 11 ms 19868 KB Output is correct
4 Correct 13 ms 19924 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 14 ms 19904 KB Output is correct
7 Correct 11 ms 19924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1807 ms 128360 KB Output is correct
2 Correct 1847 ms 132380 KB Output is correct
3 Correct 1573 ms 134240 KB Output is correct
4 Correct 2295 ms 211636 KB Output is correct
5 Correct 2561 ms 237608 KB Output is correct
6 Correct 2348 ms 226612 KB Output is correct
7 Correct 784 ms 55284 KB Output is correct
8 Correct 2578 ms 244560 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20640 KB Output is correct
2 Correct 17 ms 20700 KB Output is correct
3 Correct 18 ms 20684 KB Output is correct
4 Correct 20 ms 20684 KB Output is correct
5 Correct 2136 ms 217892 KB Output is correct
6 Correct 2339 ms 229476 KB Output is correct
7 Correct 2519 ms 236952 KB Output is correct
8 Correct 2571 ms 244496 KB Output is correct
9 Correct 507 ms 44604 KB Output is correct
10 Correct 563 ms 46872 KB Output is correct
11 Correct 567 ms 46952 KB Output is correct
12 Correct 780 ms 55256 KB Output is correct
13 Correct 2603 ms 244444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20240 KB Output is correct
2 Correct 15 ms 20512 KB Output is correct
3 Correct 18 ms 20688 KB Output is correct
4 Correct 21 ms 20804 KB Output is correct
5 Correct 1571 ms 125764 KB Output is correct
6 Correct 1914 ms 178196 KB Output is correct
7 Correct 2316 ms 225736 KB Output is correct
8 Correct 2834 ms 288548 KB Output is correct
9 Correct 2318 ms 167916 KB Output is correct
10 Correct 2739 ms 207304 KB Output is correct
11 Correct 2244 ms 167924 KB Output is correct
12 Correct 2772 ms 207384 KB Output is correct
13 Correct 2251 ms 167812 KB Output is correct
14 Correct 2734 ms 207332 KB Output is correct
15 Correct 825 ms 55292 KB Output is correct
16 Correct 2579 ms 244496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 11 ms 19924 KB Output is correct
3 Correct 11 ms 19868 KB Output is correct
4 Correct 13 ms 19924 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 14 ms 19904 KB Output is correct
7 Correct 11 ms 19924 KB Output is correct
8 Correct 1807 ms 128360 KB Output is correct
9 Correct 1847 ms 132380 KB Output is correct
10 Correct 1573 ms 134240 KB Output is correct
11 Correct 2295 ms 211636 KB Output is correct
12 Correct 2561 ms 237608 KB Output is correct
13 Correct 2348 ms 226612 KB Output is correct
14 Correct 784 ms 55284 KB Output is correct
15 Correct 2578 ms 244560 KB Output is correct
16 Correct 15 ms 20640 KB Output is correct
17 Correct 17 ms 20700 KB Output is correct
18 Correct 18 ms 20684 KB Output is correct
19 Correct 20 ms 20684 KB Output is correct
20 Correct 2136 ms 217892 KB Output is correct
21 Correct 2339 ms 229476 KB Output is correct
22 Correct 2519 ms 236952 KB Output is correct
23 Correct 2571 ms 244496 KB Output is correct
24 Correct 507 ms 44604 KB Output is correct
25 Correct 563 ms 46872 KB Output is correct
26 Correct 567 ms 46952 KB Output is correct
27 Correct 780 ms 55256 KB Output is correct
28 Correct 2603 ms 244444 KB Output is correct
29 Correct 14 ms 20240 KB Output is correct
30 Correct 15 ms 20512 KB Output is correct
31 Correct 18 ms 20688 KB Output is correct
32 Correct 21 ms 20804 KB Output is correct
33 Correct 1571 ms 125764 KB Output is correct
34 Correct 1914 ms 178196 KB Output is correct
35 Correct 2316 ms 225736 KB Output is correct
36 Correct 2834 ms 288548 KB Output is correct
37 Correct 2318 ms 167916 KB Output is correct
38 Correct 2739 ms 207304 KB Output is correct
39 Correct 2244 ms 167924 KB Output is correct
40 Correct 2772 ms 207384 KB Output is correct
41 Correct 2251 ms 167812 KB Output is correct
42 Correct 2734 ms 207332 KB Output is correct
43 Correct 825 ms 55292 KB Output is correct
44 Correct 2579 ms 244496 KB Output is correct
45 Correct 1102 ms 91348 KB Output is correct
46 Correct 1120 ms 94352 KB Output is correct
47 Correct 1216 ms 121328 KB Output is correct
48 Correct 2278 ms 211296 KB Output is correct
49 Correct 636 ms 49948 KB Output is correct
50 Correct 625 ms 49932 KB Output is correct
51 Correct 640 ms 50324 KB Output is correct
52 Correct 655 ms 50464 KB Output is correct
53 Correct 651 ms 50512 KB Output is correct
54 Correct 647 ms 50684 KB Output is correct