Submission #987166

#TimeUsernameProblemLanguageResultExecution timeMemory
987166PyqeRadio Towers (IOI22_towers)C++17
35 / 100
1281 ms157700 KiB
#include <bits/stdc++.h> #include "towers.h" using namespace std; #define mp make_pair #define fr first #define sc second const long long inf=1e18; long long n,udn=0,a[100069],uds[100069]; multiset<long long> ms; multiset<pair<long long,pair<long long,long long>>> rg; bitset<100069> spc; struct segtree { long long l,r,sm; pair<long long,long long> mxl,mxr; segtree *p[2]; void bd(long long lb,long long rb) { l=lb; r=rb; if(l==r) { sm=spc[l]; mxl={spc[l],-l}; mxr={spc[l],l}; } else { long long ii,md=(l+r)/2; for(ii=0;ii<2;ii++) { p[ii]=new segtree; p[ii]->bd(!ii?l:md+1,!ii?md:r); } sm=p[0]->sm+p[1]->sm; mxl=max(p[0]->mxl,p[1]->mxl); mxr=max(p[0]->mxr,p[1]->mxr); } } void ud(long long x,long long w) { if(l>=x&&r<=x) { sm+=w; mxl.fr+=w; mxr.fr+=w; } else { long long ii; for(ii=0;ii<2;ii++) { if(!(p[ii]->l>x||p[ii]->r<x)) { segtree *tmp=p[ii]; p[ii]=new segtree; *p[ii]=*tmp; p[ii]->ud(x,w); } } sm=p[0]->sm+p[1]->sm; mxl=max(p[0]->mxl,p[1]->mxl); mxr=max(p[0]->mxr,p[1]->mxr); } } long long qrs(long long lb,long long rb) { if(l>rb||r<lb) { return 0; } else if(l>=lb&&r<=rb) { return sm; } else { return p[0]->qrs(lb,rb)+p[1]->qrs(lb,rb); } } pair<long long,long long> qrxl(long long lb,long long rb) { if(l>rb||r<lb) { return {-inf,-1}; } else if(l>=lb&&r<=rb) { return mxl; } else { return max(p[0]->qrxl(lb,rb),p[1]->qrxl(lb,rb)); } } pair<long long,long long> qrxr(long long lb,long long rb) { if(l>rb||r<lb) { return {-inf,-1}; } else if(l>=lb&&r<=rb) { return mxr; } else { return max(p[0]->qrxr(lb,rb),p[1]->qrxr(lb,rb)); } } } sg[100069]; void init(int on,vector<int> aa) { long long i,k,l=-1,w,k2,l2; n=on; for(i=1;i<=n;i++) { a[i]=aa[i-1]; } ms.insert(-inf); ms.insert(inf); for(i=1;i<=n;i++) { if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1]))) { ms.insert(i); if(l!=-1) { rg.insert({abs(a[l]-a[i]),{l,i}}); } l=i; spc[i]=1; } } sg[0].bd(1,n); for(;!rg.empty();) { w=rg.begin()->fr; k=rg.begin()->sc.fr; l=rg.begin()->sc.sc; rg.erase(rg.begin()); if(ms.find(k)==ms.end()||ms.find(l)==ms.end()) { continue; } ms.erase(k); ms.erase(l); k2=*prev(ms.lower_bound(k)); l2=*ms.upper_bound(l); if(k2!=-inf&&l2!=inf) { rg.insert({abs(a[k2]-a[l2]),{k2,l2}}); } udn++; uds[udn]=w; sg[udn]=sg[udn-1]; sg[udn].ud(k,-1); sg[udn].ud(l,-1); } } int max_towers(int lb,int rb,int cw) { long long k,w,w2,w3,p,z; pair<long long,long long> tmp; lb++; rb++; p=lower_bound(uds+1,uds+udn+1,cw)-uds-1; w=sg[p].sm; w2=sg[p].qrs(1,lb-1); w3=sg[p].qrs(rb+1,n); z=(max(w-(w2+1)/2*2-(w3+1)/2*2,0ll)+1)/2; if(w2%2) { tmp=sg[p].qrxl(lb,rb); if(tmp.fr) { k=-tmp.sc; z+=a[k]-a[lb]>=cw; } } if(w3%2) { tmp=sg[p].qrxr(lb,rb); if(tmp.fr) { k=tmp.sc; z+=a[k]-a[rb]>=cw; } } z=max(z,1ll); return z; }
#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...