Submission #1067123

#TimeUsernameProblemLanguageResultExecution timeMemory
1067123AdamGSRadio Towers (IOI22_towers)C++17
40 / 100
1254 ms32972 KiB
#include "towers.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll INF=1e18+7; const int LIM=1e5+7; ll T[LIM], jaki[LIM], n; vector<int>trma[4*LIM]; ll trmi[4*LIM], N=1; set<pair<ll,ll>>S, P; vector<pair<ll,ll>>V; void dodaj(int x) { auto it=S.lower_bound({x, -1}); ++it; auto a=*it; P.insert({abs(T[x]-T[a.st]), x}); } void usun(int x) { auto it=S.lower_bound({x, -1}); ++it; auto a=*it; P.erase({abs(T[x]-T[a.st]), x}); } int ile(int v, int x) { if(trma[v].size()==0) return 0; if(trma[v].back()<=x) return 0; int po=0, ko=trma[v].size()-1; while(po<ko) { int sr=(po+ko)/2; if(trma[v][sr]<=x) po=sr+1; else ko=sr; } return trma[v].size()-po; } int licz(int l, int r, int x) { l+=N; r+=N; int ans=ile(l, x); if(l!=r) ans+=ile(r, x); while(l/2!=r/2) { if(l%2==0) ans+=ile(l+1, x); if(r%2==1) ans+=ile(r-1, x); l/=2; r/=2; } return ans; } int cntma(int l, int r) { l+=N; r+=N; int ans=max(trma[l].back(), trma[r].back()); while(l/2!=r/2) { if(l%2==0) ans=max(ans, trma[l+1].back()); if(r%2==1) ans=max(ans, trma[r-1].back()); l/=2; r/=2; } return ans; } int cntmi(int l, int r) { l+=N; r+=N; ll ans=min(trmi[l], trmi[r]); while(l/2!=r/2) { if(l%2==0) ans=min(ans, trmi[l+1]); if(r%2==1) ans=min(ans, trmi[r-1]); l/=2; r/=2; } return ans; } int znajdzp(int l, int r, int x) { int po=l, ko=r; while(po<ko) { int sr=(po+ko)/2; if(cntma(l, sr)<=x) po=sr+1; else ko=sr; } return po; } int znajdzs(int l, int r, int x) { int po=l, ko=r; while(po<ko) { int sr=(po+ko+1)/2; if(cntma(sr, r)<=x) ko=sr-1; else po=sr; } return po; } void init(int _n, vector<int>_H) { n=_n; while(N<n+2) N*=2; rep(i, 2*N) trmi[i]=-INF; rep(i, n) T[i+1]=_H[i]; T[0]=T[n+1]=INF; int akt=2; jaki[0]=jaki[n+1]=1; rep(i, n) if((T[i]<T[i+1] && T[i+1]>T[i+2]) || (T[i]>T[i+1] && T[i+1]<T[i+2])) { jaki[i+1]=akt; akt^=3; } rep(i, n+2) if(jaki[i]) S.insert({i, jaki[i]}); rep(i, n+2) if(!jaki[i]) trma[N+i].pb(0); auto it=S.begin(); while(true) { auto it2=it; ++it2; if(it2==S.end()) break; auto a=*it; dodaj(a.st); ++it; } V.pb({0, S.size()/2}); while(P.size()>2) { auto a=*P.begin(); usun(a.nd); trma[N+a.nd].pb(V.size()); auto it=S.lower_bound({a.nd, -1}); ++it; auto b=*it; trma[N+b.st].pb(V.size()); usun(b.st); --it; --it; b=*it; usun(b.st); ++it; S.erase(it); it=S.lower_bound({a.nd, -1}); S.erase(it); it=S.lower_bound({a.nd, -1}); --it; b=*it; dodaj(b.st); V.pb({a.st, S.size()/2}); } rep(i, n+2) if(trma[N+i].size()==0) trma[N+i].pb(V.size()+10); rep(i, n+2) trmi[N+i]=T[i]; for(int i=N-1; i; --i) { trmi[i]=min(trmi[2*i], trmi[2*i+1]); for(auto j : trma[2*i]) trma[i].pb(j); for(auto j : trma[2*i+1]) trma[i].pb(j); sort(all(trma[i])); } } int max_towers(int l, int r, int d) { ++l; ++r; int po=0, ko=V.size()-1; while(po<ko) { int sr=(po+ko+1)/2; if(V[sr].st<d) po=sr; else ko=sr-1; } int x=licz(l, r, po); if(x==0) return 1; int a=znajdzp(l, r, po), b=znajdzs(l, r, po); if(jaki[a]==2) ++x; x/=2; if(jaki[a]==1 && l<a) { if(cntmi(l, a-1)<=T[a]-d) ++x; } if(jaki[b]==1 && b<r) { if(cntmi(b+1, r)<=T[b]-d) ++x; } return x; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...