Submission #1023418

#TimeUsernameProblemLanguageResultExecution timeMemory
1023418vjudge1Shortcut (IOI16_shortcut)C++17
0 / 100
1 ms2392 KiB
#include "shortcut.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define ll long long // #define int ll #define pii pair<int,int> #define F first #define S second #define sz(s) (int)s.size() #define in insert #define pb push_back #define all(v) v.begin(),v.end() #define mem(a,i) memset(a,i,sizeof(a)) #define lb lower_bound #define ub upper_bound using namespace std; const int MAX=1e6+10; const ll inf=1e18; int n,c; vector<ll> p; pair<ll,ll> a[MAX],b[MAX]; vector<int> d; bool check(ll L){ ll sum[2][2]={{-inf,inf},{-inf,inf}}; { int r=-1; pair<ll,ll> mx={-inf,-inf},mx1={-inf,-inf}; for(int i=0;i<n;i++){ while(r+1<n&&b[r+1].F<a[i].F-L){ pair<ll,ll> bf={a[b[r+1].S].F,b[r+1].S}; if(mx<bf){ mx1=mx; mx=bf; } else if(mx1<bf){ mx1=bf; } r++; } if(i!=mx.S)sum[0][0]=max(sum[0][0],mx.F+a[i].F+c-L); else sum[0][0]=max(sum[0][0],mx1.F+a[i].F+c-L); } } { int r=-1; pair<ll,ll> mn={inf,inf},mn1={inf,inf}; for(int i=0;i<n;i++){ while(r+1<n&&b[r+1].F<a[i].F-L){ pair<ll,ll> bf={-a[b[r+1].S].F,b[r+1].S}; if(mn>bf){ mn1=mn; mn=bf; } else if(mn1>bf){ mn1=bf; } r++; } if(i!=mn.S)sum[0][1]=min(sum[0][1],L-c+a[i].S+mn.F); else sum[0][1]=min(sum[0][1],L-c+a[i].S+mn1.F); } } { int r=-1; pair<ll,ll> mn={inf,inf},mn1={inf,inf}; for(int i=0;i<n;i++){ while(r+1<n&&b[r+1].F<a[i].F-L){ pair<ll,ll> bf={b[r+1]}; if(bf<mn){ mn1=mn; mn=bf; } else if(bf<mn1){ mn1=bf; } r++; } if(mn.S!=i)sum[1][1]=min(sum[1][1],mn.F+a[i].S+L-c); if(mn1.S!=i)sum[1][1]=min(sum[1][1],mn1.F+a[i].S+L-c); } } { int r=-1; pair<ll,ll> mx={-inf,-inf},mx1={-inf,-inf}; for(int i=0;i<n;i++){ while(r+1<n&&b[r+1].F<a[i].F-L){ pair<ll,ll> bf={-b[r+1].F,b[r+1].S}; if(bf>mx){ mx1=mx; mx=bf; } else if(bf>mx1){ mx1=bf; } r++; } if(i!=mx.S)sum[1][0]=max(sum[1][0],a[i].F+mx.F+c-L); else sum[1][0]=max(sum[1][0],a[i].F+mx1.F+c-L); } } int B=-1; for(int i=0;i<n;i++){ ll l=max(sum[0][0]-p[i],p[i]-sum[0][1]),r=min(sum[1][1]-p[i],p[i]-sum[1][0]); if(l>r)break; if(i==0){ B=lb(all(p),l)-p.begin(); } while(B==-1||(B<sz(p)&&p[B]<l))B++; while(B==sz(p)||(B>=0&&p[B]>r))B--; if(B>=0&&B<sz(p)&&l<=p[B]&&p[B]<=r)return 1; } return 0; } long long find_shortcut(int N, vector<int> G, vector<int> D, int C){ n=N; c=C; d=D; p.pb(0); for(int i=1;i<n;i++)p.pb(p.back()+G[i-1]); for(int i=0;i<n;i++){ a[i]={p[i]+d[i],p[i]-d[i]}; } sort(a,a+n); for(int i=0;i<n;i++){ b[i]={a[i].S,i}; } sort(b,b+n); // check(110); // return 110; ll l=0,r=a[n-1].F-b[0].F-1,res=a[n-1].F-b[0].F; while(l<=r){ ll m=(l+r)/2; if(check(m)){ r=m-1; res=m; } else{ l=m+1; } } return res; }
#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...