No.728 ギブ and テイク - yukicoder

i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j]

jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。

あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi<jとなる添え字iについて A[i]の値をBinary Indexed Treeで管理して条件を満たすものだけ数えればいい。

const int MAX_N = 300005;
int N, A[MAX_N], L[MAX_N], R[MAX_N];

void solve() {
    cin >> N;
    rep(i, N)cin >> A[i];
    rep(i, N)cin >> L[i] >> R[i];

    // a+r<=2*10^9<INT_MAX
    priority_queue<pii, vector<pii>, greater<pii>> Q;

    BinaryIndexedTree<int> bit(N);

    ll re = 0;
    rep(i, N) {
        while (!Q.empty()) {
            auto p = Q.top();
            if (p.first >= A[i]) {
                break;
            } else {
                bit.add(p.second, -1);
                Q.pop();
            }
        }

        int p = lower_bound(A, A + N, A[i] - L[i]) - A;
        re += bit.sum(p, i);

        bit.add(i, 1);
        Q.push(mp(A[i] + R[i], i));
    }

    cout << re << endl;
}