Submission #1075066

#TimeUsernameProblemLanguageResultExecution timeMemory
1075066amirhoseinfar1385Shortcut (IOI16_shortcut)C++17
71 / 100
2066 ms17116 KiB
#include "shortcut.h" #include<bits/stdc++.h> using namespace std; const long long maxn=100000+10,lg=17,kaf=(1<<lg); long long inf=1e16,n,c; long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2; struct segmentmn{ long long seg[(1<<(lg+1))]; segmentmn(){ for(int i=0;i<kaf*2;i++){ seg[i]=inf; } } void clear(){ for(int i=0;i<kaf*2;i++){ seg[i]=inf; } } void upd(int i,long long w){ i+=kaf; seg[i]=w; i>>=1; while(i>0){ seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]); i>>=1; } } long long pors(int i,int l,int r,int tl,int tr){ if(l>r||l>tr||r<tl||tl>tr){ return inf; } if(l>=tl&&r<=tr){ return seg[i]; } int m=(l+r)>>1; return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr)); } }segmn; struct segmentmx{ long long seg[(1<<(lg+1))]; segmentmx(){ for(int i=0;i<kaf*2;i++){ seg[i]=-inf; } } void clear(){ for(int i=0;i<kaf*2;i++){ seg[i]=-inf; } } void upd(int i,long long w){ i+=kaf; seg[i]=w; i>>=1; while(i>0){ seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]); i>>=1; } } long long pors(int i,int l,int r,int tl,int tr){ if(l>r||l>tr||r<tl||tl>tr){ return -inf; } if(l>=tl&&r<=tr){ return seg[i]; } int m=(l+r)>>1; return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr)); } }segmx; void addr(long long x1,long long y1,long long x2,long long y2){ long long fx=x1+y1; long long fy=x1-y1; x1=fx; y1=fy; fx=x2+y2; fy=x2-y2; x2=fx; y2=fy; l1=max(l1,x1); l2=min(l2,x2); r1=max(r1,y2); r2=min(r2,y1); } bool dakh(long long x,long long y){ long long fx=x+y; long long fy=x-y; x=fx; y=fy; if(x>=l1&&x<=l2&&y>=r1&&y<=r2){ return 1; } return 0; } bool check(long long mid){ l1=r1=-inf; l2=r2=inf; segmx.clear(); segmn.clear(); vector<pair<long long,long long>>allv; for(int i=1;i<=n;i++){ allv.push_back(make_pair(-ps[i]+alld[i],-i)); allv.push_back(make_pair(mid-ps[i]-alld[i],i)); } sort(allv.begin(),allv.end()); while((int)allv.size()>0){ auto x=allv.back(); allv.pop_back(); if(x.second<0){ segmx.upd(-x.second,alld[-x.second]+ps[-x.second]); segmn.upd(-x.second,-alld[-x.second]+ps[-x.second]); } else{ addr(ps[x.second],-mid+c+alld[x.second]+segmx.pors(1,0,kaf-1,0,x.second-1),ps[x.second],mid-c-alld[x.second]+segmn.pors(1,0,kaf-1,0,x.second-1)); } } vector<long long>vl; for(long long i=1;i<=n;i++){ vl.push_back(ps[i]); long long l=0,r=ps[n]; l=max(l,l1-ps[i]); r=min(r,l2-ps[i]); l=max(l,-r2+ps[i]); r=min(r,-r1+ps[i]); if(r>=l){ if(vl.back()>=l){ int p=lower_bound(vl.begin(),vl.end(),l)-vl.begin(); if(vl[p]<=r){ return 1; } } } } return 0; } long long find_shortcut(int n_, std::vector<int> l, std::vector<int> d,int c_) { n=n_; c=c_; alld[1]=d[0]; for(long long i=2;i<=n;i++){ all[i]=l[i-2]; ps[i]=all[i]+ps[i-1]; alld[i]=d[i-1]; } long long low=-1,high=inf,mid; while(high-low>1){ mid=(high+low)>>1; if(check(mid)){ high=mid; }else{ low=mid; } } return high; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...