//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "shortcut.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e17 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
ll x[MAXN], d[MAXN];
pll dif[MAXN];
/*
j>i -> xi-di, xi+di are known
z+y<=len+(xj-dj)+(xi-di) -> mxsm
z+y>=(xj+dj)+(xi+di)-len -> mism
z-y<=len+(xj-dj)-(xi+di) -> mxdi
z-y>=(xj+dj)-(xi-di)-len -> midi
shortest path has to contain shortcut:
(xj+dj) - (xi-di) > k -> calc with 2 pointers
*/
bool solve(ll len, int n, ll c) {
ll mxsm = INF, mism = -INF, mxdi = INF, midi = -INF;
ll di = INF, sm = -INF;
/*pll lef = {INF, -INF};
pll rig = {-INF, -INF};*/
int l = 0, r = 0;
bool skip = false;
// calculate bounds
for (int i = 0; i < n; i++) {
while (l < r && x[i] + d[i] - dif[l].fi > len) {
int ind = dif[l++].se; // add element to set of elements producing the intersection
if (x[ind] - d[ind] < di)//lef.fi - lef.se)
di = x[ind] - d[ind];//lef = {x[ind], d[ind]};
if (x[ind] + d[ind] > sm)//rig.fi + rig.se)
sm = x[ind] + d[ind];//rig = {x[ind], d[ind]};
skip = true;
}
if (skip) {
mxsm = min(mxsm, di + x[i] - d[i] + len - c);
mism = max(mism, sm + x[i] + d[i] - len + c);
mxdi = min(mxdi, x[i] - d[i] - sm + len - c);
midi = max(midi, x[i] + d[i] - di - len + c);
}
// current station dominates last used station -> remove
// 1. cur elem (i) dominates prev (j) -> xi-di < xj-dj
// 2. prev elem (i) dominates cur (j) -> xi+di > xj+dj
// dominating elements have extremal sm and di -> inc di, dec sm
while (l < r && dif[r - 1].fi > x[i] - d[i])
r--;
dif[r++] = {x[i] - d[i], i};
}
if (mxsm < mism || mxdi < midi)
return false;
// check if there is a shortcut satisfying this bounds
int curdi = 0, cursm = n;
for (int i = 0; i < n; i++) {
while (curdi < n && x[curdi] - x[i] < midi) // violates 4.
curdi++;
// all indices >= curdi satisfy 4.
while (cursm > 0 && x[cursm - 1] + x[i] >= mism) // violates 2.
cursm--;
// all indices >= cursm satisfy 2.
int cur = max(max(cursm, curdi), i + 1); // shortcut with next element / all other combinations are checked
if (cur < n && x[cur] + x[i] <= mxsm && x[cur] - x[i] <= mxdi)
return true;
}
return false;
}
ll find_shortcut(int n, vi l, vi d2, int c) {
for (int i = 0; i < n; i++) {
d[i] = d2[i];
if (i == 0)
x[i] = 0;
else
x[i] = x[i - 1] + l[i - 1];
}
ll lo = 0, hi = INF, ret = -1;
while (lo <= hi) {
ll mi = (lo + hi) / 2;
if (solve(mi, n, c))
hi = mi - 1, ret = mi;
else
lo = mi + 1;
}
return ret;
}
