ブースを座標順に並び替えたとしても答えは変わりません。 以降、\(X_1<X_2<\ldots<X_N\) を仮定します。

\(1\leq i < j \leq N\) を満たす \((i,j)\) のうち \(X_j-X_i \leq D\) を満たすものについて \(S_i \times S_j\) の総和を求めたいです。

各 \(j\) について、 条件を満たす \(i\) は区間をなしており、それは \(l_j \leq j\) を満たす整数 \(l_j\) で \([l_j,j)\) と表せます。この \(l_j\) は \(X_{l} \geq X_j-D\) を満たす最大の \(l\) です。また、この \(l_j\) は \(j\) について単調です。

そのため、\(l_j\) は尺取り法を用いて全体で時間計算量 \(\mathrm{O}(N)\) で求めることができます。

実際に \(l_j\) を求めることができれば、\((S_{l_j}+S_{l_j+1}+\ldots+S_{j-1}) \times S_j\) を答えに加算すればよいです。$\((S_{l_j}+S_{l_j+1}+\ldots+S_{j-1}) \) は累積和を用いて 時間計算量 \(\mathrm{O}(1)\) で求めることができます。

よって、全体では最初に \(X\) でソートするのがボトルネックとなり、時間計算量 \(\mathrm{O}(N \log N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, d;
    cin >> n >> d;
    vector<pair<int, int>> xs(n);
    for (int i = 0; i < n; ++i) {
        cin >> xs[i].first >> xs[i].second;
    }
    sort(xs.begin(), xs.end());
    vector<long long> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + xs[i].second;
    long long ans = 0;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        while (l < i && xs[i].first - xs[l].first > d) l++;
        ans += (sum[i] - sum[l]) * xs[i].second;
    }
    cout << ans << endl;
}