整数 \(k\) が条件を満たすことは、頭を座標 \(k\) に置くときの各お宝までの距離を \(Y_1, \dots, Y_N\) としたとき、各 \(i\) に対し \(|\{j \, | \, Y_j \leq L_i\}| \geq i\) が成り立つことと同値です。 これを言い換えると、\(N\) 個の区間 \([X_1 - L_i, X_1 + L_i], \dots, [X_N - L_i, X_N + L_i]\) の内 \(i\) 個以上の区間が座標 \(k\) を覆う、となります。固定された \(i\) に対するこのような条件の判定は、座標昇順に調べることで高速に行うことが出来ます(実装例を参照してください)。

よって、各 \(i\) について並列に条件を管理しながら、条件を満たす整数座標の個数を加算していくことで答えを求められます。計算量は座標のソートがボトルネックで \(O(N^2 \log N)\) です。

実装例 : https://atcoder.jp/contests/abc318/submissions/45201060

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1LL<<62;

int main() {
    int N;
    cin >> N;
    vector<ll> x(N), l(N);
    for (auto &e: x) cin >> e;
    for (auto &e: l) cin >> e;
    vector<P> events;
    for (auto &e: x) {
        for (int i = 0; i < N; ++i) {
            // 第二要素の大小関係に注意 (num の加算を先に行う必要がある)
            events.emplace_back(e - l[i], i);
            events.emplace_back(e + l[i], i + N);
        }
    }
    sort(begin(events), end(events));
    ll res = 0, last = INF, check = 0;
    // num[i] := 距離 L_{i+1} 以内のお宝の個数
    vector<int> num(N, 0);
    for (auto[pos, id]: events) {
        if (id < N) {
            if ((++num[id]) == id + 1) ++check; // i = id + 1 に対する条件を満たすようになる
        } else {
            id -= N;
            if ((--num[id]) == id) --check; // i = id + 1 に対する条件を満たさなくなる
        }
        // 条件 check == N を満たす区間 [last, pos] の長さを加算
        // check < N の場合のみ、右端の分も加算
        if (last != INF) res += pos - last + (check < N ? 1 : 0);
        last = (check == N ? pos : INF);
    }
    assert(last == INF);
    cout << res << endl;
}