#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
long long lim=1000000000000000000;
long long BoundTopLeft,BoundTopRight,BoundBottomLeft,BoundBottomRight; //Where the lines that forms the current bound cuts the X-axis
long long TopLeft,TopRight,BottomLeft,BottomRight; //Where the lines that forms the current square cuts the Y-axis
int n;
long long Mainline[1100003];
long long Secondline[1100003];
long long PrefixMax[1100003];
long long PrefixMaxpos[1100003];
long long Extraline;
long long C,X,Y;
long long cntok;
long long MaxSumpos[1100003];
long long Sum[1100003];
long long Diff[1100003];
long long Curmin,CurMaxsum,MaxSumIndex,CurMindiff;
long long TreeDiameter=0;
vector <int> Dominators;
deque <int> DominatorsEnableQueue;
deque <int> MinDiffIndex;
stack <int> temp;
vector <stack<int> > EnterSquareMakingOrgy;
int P1,P2,P3,P4;
int ok;
struct NewOrder{
int ID;
int NextDominatorID;
};
bool operator< (const NewOrder &x, const NewOrder &y){
return Diff[x.ID]<Diff[y.ID];
}
NewOrder SortedByDiff[1100003];
long long PossibleDiameter(long long Dist){
BoundTopLeft=-lim;
BoundTopRight=lim;
BoundBottomLeft=-lim;
BoundBottomRight=lim;
int k;
MinDiffIndex.clear();
k=1;
for(int i=1;i<=n;i++){
if(!MinDiffIndex.empty()){
k=MinDiffIndex.back();
C=Dist-(Extraline+Secondline[i]+Secondline[k]);
X=Mainline[i];
Y=Mainline[k];
TopLeft=X-C-Y;
TopRight=X+C+Y;
BottomLeft=X-C+Y;
BottomRight=X+C-Y;
if((Secondline[i]+Secondline[k]+Mainline[i]-Mainline[k])>Dist){
BoundTopLeft=max(BoundTopLeft,TopLeft);
BoundTopRight=min(BoundTopRight,TopRight);
BoundBottomRight=min(BoundBottomRight,BottomRight);
BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
}
}
if(i==1||Diff[i]<Diff[MinDiffIndex.back()]){
MinDiffIndex.push_back(i);
}
}
k=1;
Dominators.clear();
Dominators.push_back(0);
EnterSquareMakingOrgy.clear();
for(int i=1;i<=n;i++){
if(Sum[i]>Sum[Dominators.back()]){
Dominators.push_back(i);
}
}
for(int i=0;i<=Dominators.size()+1;i++){
EnterSquareMakingOrgy.push_back(temp);
}
CurMaxsum=-lim;
int Pointer=1;
MaxSumIndex=1;
for(int i=2;i<Dominators.size();i++){
while(Pointer<=n&&Sum[Dominators[i]]-Diff[SortedByDiff[Pointer].ID]>Dist){
EnterSquareMakingOrgy[max(i,SortedByDiff[Pointer].NextDominatorID)].push(SortedByDiff[Pointer].ID);
Pointer++;
}
while(!EnterSquareMakingOrgy[i].empty()){
if(CurMaxsum<Sum[EnterSquareMakingOrgy[i].top()]){
CurMaxsum=Sum[EnterSquareMakingOrgy[i].top()];
MaxSumIndex=EnterSquareMakingOrgy[i].top();
}
EnterSquareMakingOrgy[i].pop();
}
k=MaxSumIndex;
C=Dist-(Extraline+Secondline[Dominators[i]]+Secondline[k]);
X=Mainline[Dominators[i]];
Y=Mainline[k];
TopLeft=X-C-Y;
TopRight=X+C+Y;
BottomLeft=X-C+Y;
BottomRight=X+C-Y;
if((Secondline[Dominators[i]]+Secondline[k]+Mainline[Dominators[i]]-Mainline[k])>Dist){
BoundTopLeft=max(BoundTopLeft,TopLeft);
BoundTopRight=min(BoundTopRight,TopRight);
BoundBottomRight=min(BoundBottomRight,BottomRight);
BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
}
}
if(BoundTopLeft>BoundBottomRight||BoundBottomLeft>BoundTopRight){
return 0;
}
P1=1;
P2=n+1;
P3=1;
P4=n+1;
ok=0;
while(Mainline[P1]<BoundTopLeft&&P1<=n){
P1++;
}
while(Mainline[P3]<BoundBottomLeft&&P3<=n){
P3++;
}
while(Mainline[P2]>BoundBottomRight&&P2>1){
P2--;
}
while(Mainline[P4]>BoundTopRight&&P4>1){
P4--;
}
if(P1<=P2&&P3<=P4){
if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
ok=1;
return ok;
}
}
for(int i=2;i<=n;i++){
while(Mainline[P1]-Mainline[i]<BoundTopLeft&&P1<=n){
P1++;
}
while(Mainline[P2+1]-Mainline[i]<=BoundBottomRight&&P2<=n){
P2++;
}
while(Mainline[i]+Mainline[P3-1]>=BoundBottomLeft&&P3>1){
P3--;
}
while(Mainline[i]+Mainline[P4]>BoundTopRight&&P4>=1){
P4--;
}
if(P1<=P2&&P3<=P4){
if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
ok=1;
return ok;
}
}
}
return ok;
}
long long find_shortcut(int N, vector <int> L, vector <int> D, int C){
n=N;
Extraline=C;
long long temp=0;
for(int i=2;i<=n;i++){
temp=L[i-2];
Mainline[i]=Mainline[i-1]+temp;
}
Mainline[n+1]=lim;
Curmin=lim;
CurMindiff=lim;
for(int i=1;i<=n;i++){
Secondline[i]=D[i-1];
Sum[i]=Mainline[i]+Secondline[i];
Diff[i]=Mainline[i]-Secondline[i];
if(i>=2){
TreeDiameter=max(TreeDiameter,Sum[i]-CurMindiff);
}
CurMindiff=min(CurMindiff,Diff[i]);
}
long long l=1,r=TreeDiameter;
Dominators.clear();
Dominators.push_back(0);
for(int i=1;i<=n;i++){
if(Sum[i]>Sum[Dominators.back()]){
Dominators.push_back(i);
}
SortedByDiff[i]={i,Dominators.size()};
}
sort(SortedByDiff+1,SortedByDiff+n+1);
long long mid;
while(r-l>1){
mid=(r+l)/2;
if(PossibleDiameter(mid)){
r=mid;
}else{
l=mid+1;
}
}
if(PossibleDiameter(l)){
return l;
}else if(PossibleDiameter(r)){
return r;
}
}
