#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> edge;
const int MAXN = 3e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
int N;
ll C;
ll L[MAXN]; //total length
ll D[MAXN]; //distance to secondary station (i + N)
//max BIT - wow that actually sped things up!
struct fenwick {
ll bit[MAXN];
void reset() {
fill_n(bit, MAXN, LLONG_MIN);
}
void update (int x, ll v) {
for (x++; x < MAXN; x += (x & -x)) {
setmax(bit[x], v);
}
}
ll query (int x) {
//query to x EXCLUSIVE
ll res = LLONG_MIN;
for (; x; x &= (x - 1)) {
setmax(res, bit[x]);
}
return res;
}
};
fenwick fenlpd, fendml;
pair<ll, int> vlmd[MAXN], vlpd[MAXN];
bool moo_slow (ll dia);
bool moo (ll dia) {
//debug("DIA = %lld\n", dia);
//return moo_slow(dia);
ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;
//reset entire fenwick tree
fenlpd.reset();
fendml.reset();
//vlpd[vj].fi - vlmd[vi].fi > dia
for (int vj = 0, vi = 0; vj < N; vj++) {
int j = vlpd[vj].se;
for (; vi < N && vlpd[vj].fi - vlmd[vi].fi > dia; vi++) {
//add vi
int i = vlmd[vi].se;
fenlpd.update(i, L[i] + D[i]);
fendml.update(i, D[i] - L[i]);
//debug("i = %d, j = %d. Distance = %lld\n", i, j, vlpd[vj].fi - vlmd[vi].fi);
}
//setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C);
//setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C);
//setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C);
//setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C);
ll qulpd = fenlpd.query(j), qudml = fendml.query(j);
if (qulpd != LLONG_MIN) {
setmax(xmymn, qulpd + (-L[j] + D[j]) - dia + C);
setmin(xmymx, -qudml + (-L[j] - D[j]) + dia - C);
if (xmymn > xmymx) {
return false;
}
setmax(xpymn, qulpd + (L[j] + D[j]) - dia + C);
setmin(xpymx, -qudml + (L[j] - D[j]) + dia - C);
if (xpymn > xpymx) {
return false;
}
}
}
//debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx);
//basic checks
if (xmymn == LLONG_MIN) {
return true;
}
for (int j = 1; j < N; j++) {
ll xmn = max(xpymn - L[j], xmymn + L[j]);
ll xmx = min(xpymx - L[j], xmymx + L[j]);
if (xmn > xmx) {
continue;
}
if (upper_bound(L, L + j, xmx) != lower_bound(L, L + j, xmn)) {
return true;
}
}
return false;
}
ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) {
//very very preliminary stuff - should also init other stuff
N = nnn;
C = ccc;
L[0] = 0;
for (int i = 1; i < N; i++) {
L[i] = L[i - 1] + lll[i - 1];
}
for (int i = 0; i < N; i++) {
D[i] = ddd[i];
}
//precomp here!
for (int i = 0; i < N; i++) {
vlmd[i] = make_pair(L[i] - D[i], i);
vlpd[i] = make_pair(L[i] + D[i], i);
}
sort(vlmd, vlmd + N);
sort(vlpd, vlpd + N);
ll lo = 0, hi = (N + 1) * 1000000000ll;
while (hi - lo > 1) {
ll mid = (lo + hi) >> 1;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
bool moo_slow (ll dia) {
//is diameter <= dia?
ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if ((L[j] + D[j]) - (L[i] - D[i]) > dia) {
//ll lim = dia - D[i] - D[j] - C;
//L[i] - L[j] - lim <= x - y <= L[i] - L[j] + lim
//L[i] + L[j] - lim <= x + y <= L[i] + L[j] + lim
setmax(xmymn, (L[i] + D[i]) + (-L[j] + D[j]) - dia + C);
setmin(xmymx, (L[i] - D[i]) + (-L[j] - D[j]) + dia - C);
setmax(xpymn, (L[i] + D[i]) + (L[j] + D[j]) - dia + C);
setmin(xpymx, (L[i] - D[i]) + (L[j] - D[j]) + dia - C);
}
//otherwise everything works
}
}
//debug("x - y: min = %lld, max = %lld.\nx + y: min = %lld, max = %lld.\n", xmymn, xmymx, xpymn, xpymx);
if (xmymn > xmymx || xpymn > xpymx) {
return false;
}
debug("xmymn = %lld, xmymx = %lld. xpymn = %lld, xpymx = %lld.\n", xmymn, xmymx, xpymn, xpymx);
if (xmymn == LLONG_MIN) {
return true;
}
//ok now check if anything is in there
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (xmymn <= L[i] - L[j] && L[i] - L[j] <= xmymx) {
if (xpymn <= L[i] + L[j] && L[i] + L[j] <= xpymx) {
return true;
}
}
}
}
return false;
}
