#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;
const int mxN = 1e6+5;
const ll mxX = 1e17;
int N, C, D[mxN];
ll X[mxN];
int id1[mxN], id2[mxN];
bool check(ll k) {
int i = 1;
ll b[] = { -mxX, mxX, -mxX, mxX }; // min/max y+z, min/max y-z
ll v[] = { -mxX, -mxX, mxX, mxX }; // max X[I]+D[i], min X[I]-D[I]
int s[] = { -1, -1, -1, -1 }; // ids for v
FOR(j,1,N){
int I = id1[i], J = id2[j];
while (i <= N && (X[J]+D[J])-(X[I]-D[I]) > k) {
if (X[I]+D[I] > v[0]) v[0] = X[I]+D[I], s[0] = I;
if (v[0] > v[1]) swap(v[0],v[1]), swap(s[0],s[1]);
if (X[I]-D[I] < v[2]) v[2] = X[I]-D[I], s[2] = I;
if (v[2] < v[3]) swap(v[2],v[3]), swap(s[2],s[3]);
b[0] = max(b[0], -k+C+(X[J]+D[J])+(J==s[1]?v[0]:v[1]));
b[1] = min(b[1], k-C+(X[J]-D[J])+(J==s[3]?v[2]:v[3]));
b[2] = max(b[2], -k+C-(X[J]-D[J])+(J==s[1]?v[0]:v[1]));
b[3] = min(b[3], k-C-(X[J]+D[J])+(J==s[3]?v[2]:v[3]));
I = id1[++i];
}
}
int l = 1, r = 0; // move only O(N) times
FOR(i,1,N){
while (l > 1 && X[l-1] >= max(b[0]-X[i],b[2]+X[i])) --l;
while (r < N && X[r+1] <= min(b[1]-X[i],b[3]+X[i])) ++r;
while (l <= N && X[l] < max(b[0]-X[i],b[2]+X[i])) ++l;
while (r >= 1 && X[r] > min(b[1]-X[i],b[3]+X[i])) --r;
if (l <= r) return 1; // found a shortcut
}
return 0;
}
ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
N = n, C = c;
X[1] = 0;
FOR(i,2,N) X[i] = X[i-1] + l[i-2];
int mx = 0, smx = 0;
FOR(i,1,N){
D[i] = d[i-1];
if (D[i] > smx) smx = D[i];
if (smx > mx) swap(smx,mx);
}
FOR(i,1,N) id1[i] = id2[i] = i;
sort(id1+1,id1+1+N,[](int a, int b){
ll p = X[a]-D[a], q = X[b]-D[b];
return (p == q ? a < b : p < q);
});
sort(id2+1,id2+1+N,[](int a, int b){
ll p = X[a]+D[a], q = X[b]+D[b];
return (p == q ? a < b : p < q);
});
ll lo = mx+smx-1, hi = mxX;
while (hi-lo > 1){
ll mid = (lo+hi)/2;
if (check(mid)) hi = mid;
else lo = mid;
}
return hi;
}
