#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
#pragma "O3"
const ll OO = (ll)1e14;
template<ll (*op)(ll&, ll&), ll NULLVAL>
struct Fenwick {
int N;
vector<int> tree;
void reset (int n) {
N = n;
tree.assign(N+1, NULLVAL);
}
int query (int idx) {
ll res = NULLVAL;
idx++;
while (idx > 0) {
res = op(res, tree[idx]);
idx -= idx&(-idx);
}
return res;
}
void update (int idx, ll val) {
idx++;
while (idx <= N) {
tree[idx] = op(tree[idx], val);
idx += idx&(-idx);
}
}
};
ll maxi (ll& a, ll& b) {return max(a, b);}
ll mini (ll& a, ll& b) {return min(a, b);}
vector<int> incR, decL;
Fenwick<maxi, -OO> xMinQ;
Fenwick<mini, OO> xMaxQ;
Fenwick<maxi, -OO> yMinQ;
Fenwick<mini, OO> yMaxQ;
bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
// x = r-l, y = r+l
xMinQ.reset(N);
xMaxQ.reset(N);
yMinQ.reset(N);
yMaxQ.reset(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(iR-1));
xMax = min(xMax, dist[iR] - lenDown[iR] + UB - costBridge + xMaxQ.query(iR-1));
yMin = max(yMin, dist[iR] + lenDown[iR] - UB + costBridge + yMinQ.query(iR-1));
yMax = min(yMax, dist[iR] - lenDown[iR] + UB - costBridge + yMaxQ.query(iR-1));
}
// cerr << "UB: " << UB << ", " << xMin << " " << xMax << ", " << yMin << " " << yMax << "\n";
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])) {
return true;
}
}
return false;
}
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];
assert(dist[i] < dist[i+1]);
}
incR.assign(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]);
});
decL.assign(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]);
});
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;
}
