#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 100100;
const ll INF = 1e17;
int n;
ll c;
ll l[MAXN];
ll d[MAXN];
ll x[MAXN];
vl xs;
ll a[MAXN], b[MAXN];
vector<pair<ll, int>> srtB, srtA;
int idToUpd[MAXN], idToGet[MAXN];
ll tree[4 * MAXN][4];
void build (int index, int id = 1, int le = 0, int ri = n - 1) {
if (le == ri) {
tree[id][index] = -INF;
return;
}
int mid = (le + ri) / 2;
build (index, 2 * id, le, mid);
build (index, 2 * id + 1, mid + 1, ri);
tree[index][id] = max(tree[index][2 * id], tree[index][2 * id + 1]);
}
void upd (int index, int p, ll kx, int id = 1, int le = 0, int ri = n - 1) {
if (le == ri) {
tree[id][index] = kx;
return;
}
int mid = (le + ri) / 2;
if (p <= mid) {
upd(index, p, kx, 2 * id, le, mid);
}
else {
upd(index, p, kx, 2 * id + 1, mid + 1, ri);
}
tree[id][index] = max(tree[2 * id][index], tree[2 * id + 1][index]);
}
ll get (int index, int kx, int y, int id = 1, int le = 0, int ri = n - 1) {
if (kx > ri || y < le) {
return 0ll;
}
if (kx <= le && ri <= y) {
return tree[id][index];
}
int mid = (le + ri) / 2;
return max(get(index, kx, y, 2 * id, le, mid), get(index, kx, y, 2 * id + 1, mid + 1, ri));
}
bool doesExist (ll mn1, ll mx1, ll mn2, ll mx2) {
/*FOR(y, 0, n-1) FOR(z, 0, n-1) {
if (mn1 <= x[y]+x[z] && x[y]+x[z] <= mx1 && mn2 <= x[z]-x[y] && x[z]-x[y] <= mx2)
return true;
}
return false;*/
FOR(z, 0, n - 1) {
ll mnY = max(mn1 - x[z], x[z] - mx2);
ll mxY = min(mx1 - x[z], x[z] - mn2);
auto it = lower_bound(xs.begin(), xs.end(), mnY);
if (it != xs.end()) {
ll num = (*it);
if (num <= mxY) {
return true;
}
}
}
return false;
}
bool check (ll k) {
//cout << "----------------------\nk = " << k << endl;
ll mn1 = -INF, mn2 = -INF, mx1 = INF, mx2 = INF;
//ll mnA = INF, mxA = -INF, mnB = INF, mxB = -INF;
//FOR(i, 0, 3) build(i);
FOR(i, 1, 2) build(i);
//int rId = 0;
FOR(i, 0, n - 1) {
idToUpd[srtB[i].s] = i;
//cout << " i=" << i << " srtB = " << srtB[i].f << " id=" << srtB[i].s << endl;
// while (rId < n && srtA[rId].f - k <= srtB[i].s) {
// idToGet[srtA[rId].s] = i-1;
// rId++;
// }
}
// int le = 0;
FOR(j, 0, n - 1) {
int kj = 0;
int le = 0, ri = n - 1;
while (le < ri) {
int mid = (le + ri + 1) / 2;
//cout << " " << srtB[mid].f << " " << a[j]-k << endl;
if (srtB[mid].f < a[j] - k) {
le = mid;
}
else {
ri = mid - 1;
}
}
//le = min(le, ri);
if (a[j] - k <= srtB[le].f) {
le--;
}
//cout << " j=" << j << " aj-k=" << a[j]-k << " le= " << le << endl;
kj = le;
//ll mnA = (-1ll)*(get(0, 0,kj));
ll mxA = (get(1, 0, kj));
ll mnB = (-1ll) * (get(2, 0, kj));
// ll mxB = (get(3, 0,kj));
//cout << " j=" << j
if (mxA > 0) {
mn1 = max(mn1, mxA + a[j] - (k - c));
//mn1 = max(mn1, mnA + a[j] - (k-c));
mx1 = min(mx1, mnB + b[j] + (k - c));
//mx1 = min(mx1, mxB + b[j] + (k-c));
mn2 = max(mn2, a[j] - mnB - (k - c));
//mn2 = max(mn2, a[j] - mxB - (k-c));
mx2 = min(mx2, b[j] - mxA + (k - c));
//mx2 = min(mx2, b[j] - mnA + (k-c));
}
kj = idToUpd[j];
// upd(0, kj, (-a[j]));
upd(1, kj, (a[j]));
upd(2, kj, (-b[j]));
// upd(3, kj, (b[j]));
}
return doesExist(mn1, mx1, mn2, mx2);
}
ll solve () {
x[0] = 0;
FOR(i, 1, n - 1) x[i] = x[i - 1] + l[i - 1];
FOR(i, 0, n - 1) xs.pb(x[i]);
FOR(i, 0, n - 1) a[i] = x[i] + d[i];
FOR(i, 0, n - 1) b[i] = x[i] - d[i];
FOR(i, 0, n - 1) srtA.pb({a[i], i});
FOR(i, 0, n - 1) srtB.pb({b[i], i});
sort(srtA.begin(), srtA.end());
sort(srtB.begin(), srtB.end());
ll le = 0, ri = 2 * (1e14);
while (le < ri) {
ll mid = (le + ri) / 2;
if (check(mid)) {
ri = mid;
}
else {
le = mid + 1;
}
}
return le;
}
long long find_shortcut(int _n,vector<int> _l,vector<int> _d,int _c) {
n = _n;
c = _c;
FOR(i, 0, n-2) l[i] = (el);
FOR(i, 0, n-1) d[i] = (el);
return solve();
}
/*inline int read()
{
int x=0,f=1;char ch=getchar();
//while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}*/
/*int main()
{
//FAST_IO;
//cin >> n >> c;
//FOR(i, 0, n - 2) cin >> l[i];
//FOR(i, 0, n - 1) cin >> d[i];*
n = read();
c = read();
FOR(i, 0, n-2) l[i] = read();
FOR(i, 0, n-1) d[i] = read();
cout << solve() << "\n";
return 0;
}*/
/*
4 10
10 20 20
0 40 0 30
ans: 80
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
ans: 110
4 1
2 2 2
1 10 10 1
ans: 21
3 3
1 1
1 1 1
ans: 4
*/
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:213:28: error: 'el' was not declared in this scope
FOR(i, 0, n-2) l[i] = (el);
^~
shortcut.cpp:213:28: note: suggested alternative: '_l'
FOR(i, 0, n-2) l[i] = (el);
^~
_l
shortcut.cpp:214:28: error: 'el' was not declared in this scope
FOR(i, 0, n-1) d[i] = (el);
^~
shortcut.cpp:214:28: note: suggested alternative: '_l'
FOR(i, 0, n-1) d[i] = (el);
^~
_l
