This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "shortcut.h"
ll n,c,i,j,u,v,x[1000005],h[1000005],tight1,tight2,tight3,tight4;
II mx_sum1,mx_sum2,mx_sub1,mx_sub2;
const ll oo=round(1e18);
struct Sparse_Table
{
ll rmq[1000005][21],bin[1000005];
void Add(int i,ll k)
{
bin[i]=Log(i);
rmq[i][0]=k;
for(int j=1;j<=bin[i];j++)
rmq[i][j]=max(rmq[i][j-1],rmq[i-(1<<(j-1))][j-1]);
}
ll Get(int l,int r)
{
if(l>r) return -oo;
int k=bin[r-l+1];
return max(rmq[r][k],rmq[l+(1<<k)-1][k]);
}
} RMQ_sum,RMQ_sub;
bool Add_edge(int u,int v,ll k)
{
if(c>=x[v]-x[u]) return 0;
ll Before=RMQ_sub.Get(1,u-1),After=RMQ_sum.Get(v+1,n);
if(x[u]+Before+After-x[v]+c>k) return 0;
int j=u-1;
for(int i=u;i<=v;i++)
{
if(h[i]+min(x[i]-x[u],x[v]-x[i]+c)+x[u]+Before>k) return 0;
if(h[i]+min(x[v]-x[i],x[i]-x[u]+c)+After-x[v]>k) return 0;
while(j+1<i && x[j+1]-x[u]+c+x[v]-x[i]<x[i]-x[j+1]) j++;
if(h[i]+x[v]-x[i]+c+RMQ_sum.Get(u,j)-x[u]>k) return 0;
if(h[i]+x[i]+RMQ_sub.Get(j+1,i-1)>k) return 0;
}
return 1;
}
bool check(ll k)
{
if(k==tight3) return 1;
tight1=tight2=-1e18;
for(i=1;i<=n;i++)
{
if(mx_sum2.snd!=i) j=mx_sum2.snd; else j=mx_sum1.snd;
if(h[j]+x[j]+h[i]-x[i]<=k) continue;
tight1=max(tight1,h[j]+x[j]+h[i]+x[i]);
}
for(j=1;j<=n;j++)
{
if(mx_sub2.snd!=j) i=mx_sub2.snd; else i=mx_sub1.snd;
if(h[j]+x[j]+h[i]-x[i]<=k) continue;
tight2=max(tight2,h[j]-x[j]+h[i]-x[i]);
}
ll l=n+1,r=0,opt=oo;
for(i=1;i<=n;i++)
{
while(l>1 && x[l-1]>=-x[i]-k+c+tight1) l--;
while(r<n && x[r+1]<=min(k-c-tight2-x[i],k-c-tight3+x[i])) r++;
while(r>0 && x[r]>min(k-c-tight2-x[i],k-c-tight3+x[i])) r--;
if(l>r || l>i) continue;
ll j=min(r,i);
if(opt>x[i]-x[j])
{
opt=x[i]-x[j];
u=j; v=i;
}
}
if(opt==oo) return 0;
return Add_edge(u,v,k);
}
ll find_shortcut(int _n,vector <int> len,vector <int> d,int _c)
{
n=_n; c=_c;
ll dis=0;
for(i=0;i<len.size();i++) x[i+1]=dis,dis+=len[i];
x[n]=dis;
for(i=0;i<d.size();i++) h[i+1]=d[i];
mx_sum1=mx_sum2=mx_sub1=mx_sub2={ -oo,0 };
for(i=1;i<=n;i++)
{
if(mx_sum1.fst<h[i]+x[i]) mx_sum1={ h[i]+x[i],i };
if(mx_sum1.fst>mx_sum2.fst) swap(mx_sum1,mx_sum2);
if(mx_sub1.fst<h[i]-x[i]) mx_sub1={ h[i]-x[i],i };
if(mx_sub1.fst>mx_sub2.fst) swap(mx_sub1,mx_sub2);
}
for(i=1;i<=n;i++)
{
RMQ_sum.Add(i,h[i]+x[i]);
RMQ_sub.Add(i,h[i]-x[i]);
}
ll ma=-oo;
for(i=1;i<=n;i++)
{
tight3=max(tight3,h[i]+x[i]+ma);
ma=max(ma,h[i]-x[i]);
}
ll l=0,r=tight3;
while(l<r)
{
ll mid=(l+r)>>1;
if(check(mid)) r=mid; else l=mid+1;
}
return l;
}
/*
int main()
{
freopen("shortcut.inp","r",stdin);
freopen("shortcut.out","w",stdout);
int n,c,x;
vector <int> l,d;
cin>>n>>c;
for(i=1;i<n;i++) cin>>x,l.push_back(x);
for(i=1;i<=n;i++) cin>>x,d.push_back(x);
cout<<find_shortcut(n,l,d,c);
}
*/
Compilation message (stderr)
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:94:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(i=0;i<len.size();i++) x[i+1]=dis,dis+=len[i];
| ~^~~~~~~~~~~
shortcut.cpp:96:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(i=0;i<d.size();i++) h[i+1]=d[i];
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |