概要

座標差が \(D\) 以下のブースの組 \((i,j)\) について、相乗効果 \(S_i \times S_j\) の総和を求めます。座標でソートし、尺取り法（2 ポインタ）で「近いブース集合」を保ちながら高速に合計します。

考察

求めたいのは [ \sum_{1\le i\le N,\ |X_i-X_j|\le D} S_iS_j ] です。

素朴解がダメな理由

全ペアを調べると \(O(N^2)\) で、\(N\le 2\times 10^5\) では最大約 \(2\times 10^{10}\) ペアになり、時間内に終わりません（TLE）。

重要な観察

• \(X_i\) はすべて異なり、一直線上の座標なので、座標で昇順にソートすると距離条件が扱いやすくなります。
• ソート後、あるブース \(j\) を右端として見ると、条件 \(|X_i-X_j|\le D\) は（\(i<j\) の範囲では） [ X_j - X_i \le D ] だけを見ればよく、左側に「条件を満たす連続区間」ができます。

どう解決するか

右端 \(j\) を左から順に動かしながら、 - 条件を満たす最小の左端 \(left\) を進めて調整（尺取り法） - 区間 \([left,\,j-1]\) にいるブースの集客力の和を \(sum\_s\) として持つ

とすると、ブース \(j\) と組める相手の相乗効果の合計は [ Sj \times \sum{i=left}^{j-1} S_i = S_j \times sum_s ] で一発で足せます。

（例）\(S_j=5\) で、近い左側の \(S\) が \(2,3,4\) なら、相乗効果は \(5\times2+5\times3+5\times4=5\times(2+3+4)\) です。

アルゴリズム

1. 入力された \((X_i,S_i)\) を \(X\) の昇順にソートする。
2. 2 ポインタ \(left, right\) と、現在の有効区間（\(right\) の左側で距離条件を満たす集合）の集客力和 \(sum\_s\) を用意する。
3. \(right=0..N-1\) を順に処理する：
   • \(X_{right} - X_{left} > D\) の間、\(left\) を右に動かし、除外するブースの \(S\) を \(sum\_s\) から引く。
   • この時点で、\(left..right-1\) が「\(right\) と距離 \(D\) 以内」の全ブース。
   • 答えに \(S_{right} \times sum\_s\) を加える（\(right\) と組める全ペア分）。
   • \(sum\_s\) に \(S_{right}\) を足し、次の \(right\) に備える。
4. 最終的な答えを出力する。

この方法では、各ブースは \(left/right\) により高々 1 回ずつ区間に入ったり出たりするだけなので、走査部分は \(O(N)\) で済みます。

計算量

• 時間計算量: ソートが \(O(N\log N)\)、尺取り走査が \(O(N)\) なので全体で \(O(N\log N)\)
• 空間計算量: 入力配列の保持に \(O(N)\)

実装のポイント

• 必ず座標でソートしてから尺取りを行います（これにより「条件を満たす相手が連続区間」になる）。

• \(sum\_s\) は「現在の有効区間の \(S\) の総和」を常に正しく保つ（左端を動かすときに引く／右端を追加するときに足す）。

• 答えは最大で \(2^{63}-1\) 以下が保証されています。Python の int は多倍長なのでそのままで安全です（他言語なら 64bit 整数を使用）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    booths = [tuple(map(int, input().split())) for _ in range(N)]
    booths.sort()  # sort by X

    left = 0
    sum_s = 0
    ans = 0

    for right in range(N):
        x_r, s_r = booths[right]
        while left < right and x_r - booths[left][0] > D:
            sum_s -= booths[left][1]
            left += 1
        ans += s_r * sum_s
        sum_s += s_r

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。