Sol:

$pos_j – pos_i + h_i + h_j \leq mid \tag 1 \label 1$
$h_i + h_j + | pos_j – pos_b | + |pos_i – pos_a | + len \leq mid \tag 2 \label 2$

$\eqref 1$式等价于 $z_j + y_i \leq mid$，$\eqref 2$式可以通过拆绝对值，转化成四个关于 $\pm pos_a \pm pos_b\leq limit$的方程，之后双指针扫描边界就行了。

#include <bits/stdc++.h>
#include "shortcut.h"
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

const lo inf = 1e18;
const int N = 2e6 + 233;
int n, vs;
lo len, pre[N], np[N], h[N];

inline bool check(lo mid) {
lo A = -inf, B = -inf, C = -inf, D = -inf;
lo Neg = -inf, Pos = -inf;
deque <int> q;
for (int j = 1; j <= n; j++) {
while (q.size()) {
int i = q.front();
if (pre[j] - pre[i] + h[i] + h[j] > mid) {
Neg = max(Neg, h[i] + pre[i]);
Pos = max(Pos, h[i] - pre[i]);
q.pop_front();
} else break;
}
A = max(A, h[j] + pre[j] + Neg);
C = max(C, h[j] + pre[j] + Pos);
B = max(B, h[j] - pre[j] + Neg);
D = max(D, h[j] - pre[j] + Pos);
while (q.size() && h[q.back()] - pre[q.back()] < h[j] - pre[j]) q.pop_back();
q.push_back(j);
}
A = mid - len - A; B = mid - len - B;
C = mid - len - C; D = mid - len - D;
int lx = 1, rx = 1, ly = n, ry = n;
for (int b = 1; b <= n; b++) {
while (lx <= n && !(np[lx] >= np[b] - B)) lx++;
while (rx + 1 <= n && np[rx + 1] <= C + np[b]) rx++;
while (ly - 1 >= 1 && np[ly - 1] >= -np[b] - A) ly--;
while (ry >= 1 && !(np[ry] <= -np[b] + D)) ry--;
if (ly > ry || lx > rx) continue;
if (!(rx < ly || ry < lx)) return true;
}
return false;
}

lo find_shortcut(int _n, vector<int> _l, vector<int> d, int c) {
n = _n; len = c;
pre[1] = 0;
rep (i, n) pre[i + 1] = _l[i - 1] + pre[i];
memcpy(np, pre, sizeof np);
sort(np + 1, np + n + 1);
rep (i, n) h[i] = d[i - 1];
lo l = *max_element(h + 1, h + n + 1), r = 0, prefix = 0;
rep (i, n) {
r = max(r, prefix + pre[i] + h[i]);
prefix = max(prefix, h[i] - pre[i]);
}
while (l < r) {
lo mid = l + (r - l) / 2;
check(mid) ? r = mid : l = mid + 1;
}
return r;
}