#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
const ll OO = (ll)1e18;
template<ll (*op)(ll&, ll&), ll NULLVAL>
struct Segtree {
int numleaves;
vector<ll> tree;
Segtree (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2;
tree.assign(2*numleaves, NULLVAL);
}
ll query (int l, int r) {
ll res = NULLVAL;
l += numleaves, r += numleaves+1;
while (l < r) {
if (l&1) {
res = op(res, tree[l++]);
}
if (r&1) {
res = op(res, tree[--r]);
}
l /= 2, r /= 2;
}
return res;
}
void update (int idx, ll val) {
idx += numleaves;
tree[idx] = val;
idx /= 2;
while (idx > 0) {
tree[idx] = op(tree[2*idx], tree[2*idx+1]);
idx /= 2;
}
}
};
ll maxi (ll& a, ll& b) {return max(a, b);}
ll mini (ll& a, ll& b) {return min(a, b);}
bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
vector<int> incR(N, 0);
iota(incR.begin(), incR.end(), 0);
sort(incR.begin(), incR.end(), [&](const int& a, const int& b)->bool{
return (dist[a] + lenDown[a] < dist[b] + lenDown[b]);
});
vector<int> decL(N, 0);
iota(decL.begin(), decL.end(), 0);
sort(decL.begin(), decL.end(), [&](const int& a, const int& b)->bool{
return (-dist[a] + lenDown[a] > -dist[b] + lenDown[b]);
});
// x = r-l, y = r+l
Segtree<maxi, -OO> xMinQ(N);
Segtree<mini, OO> xMaxQ(N);
Segtree<maxi, -OO> yMinQ(N);
Segtree<mini, OO> yMaxQ(N);
ll xMin = -OO, xMax = OO, yMin = -OO, yMax = OO;
int iDecL = 0;
for (int iIncR = 0; iIncR < N; iIncR++) {
int iR = incR[iIncR];
while (iDecL < N && (-dist[decL[iDecL]] + lenDown[decL[iDecL]]) > UB - (dist[iR] + lenDown[iR])) {
int iL = decL[iDecL];
xMinQ.update(iL, -dist[iL] + lenDown[iL]);
xMaxQ.update(iL, -dist[iL] - lenDown[iL]);
yMinQ.update(iL, dist[iL] + lenDown[iL]);
yMaxQ.update(iL, dist[iL] - lenDown[iL]);
iDecL++;
}
xMin = max(xMin, dist[iR] + lenDown[iR] - UB + costBridge + xMinQ.query(0, iR-1));
xMax = min(xMax, dist[iR] - lenDown[iR] + UB - costBridge + xMaxQ.query(0, iR-1));
yMin = max(yMin, dist[iR] + lenDown[iR] - UB + costBridge + yMinQ.query(0, iR-1));
yMax = min(yMax, dist[iR] - lenDown[iR] + UB - costBridge + yMaxQ.query(0, iR-1));
}
// cerr << "UB: " << UB << ", " << xMin << " " << xMax << ", " << yMin << " " << yMax << "\n";
bool res = false;
for (int iL = 0; iL < N-1; iL++) {
int iR = lower_bound(dist.begin(), dist.end(), max(xMin + dist[iL], yMin - dist[iL])) - dist.begin();
if (iR < N && dist[iR] <= min(xMax + dist[iL], yMax - dist[iL])) {
res = true;
}
}
return res;
}
ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
vector<ll> dist(N, 0);
for (int i = 0; i < N-1; i++) {
dist[i+1] = dist[i] + lenSide[i];
}
ll loBS = 0, hiBS = OO;
while (loBS < hiBS-1) {
ll midBS = loBS + (hiBS - loBS) / 2;
assert(loBS <= midBS && midBS <= hiBS);
if (test(midBS, N, dist, lenDown, costBridge)) {
hiBS = midBS;
}
else {
loBS = midBS;
}
}
return hiBS;
}
