Overview

Given \(N\) booths arranged on a one-dimensional line, find the total sum of products of attraction powers (synergy effects) for all pairs of booths that are within distance \(D\) of each other.

Analysis

In this problem, for every pair of booths \((i, j)\), if the distance \(|X_i - X_j| \leq D\), we need to add \(S_i \times S_j\) to the answer.

Naive Approach (Why it TLEs)

A straightforward method would be to check the distance for all pairs \((i, j)\) (\(i < j\)) and add the product if the condition is satisfied. However, this requires up to

\[ \frac{N(N - 1)}{2} \approx 2 \times 10^{10} \]

computations, which is far too slow for the constraint \(N \leq 2 \times 10^5\) (TLE).

Improvement Idea

For each booth \(i\), the set of booths \(j\) (\(j > i\)) within distance \(D\) forms a contiguous interval when the coordinates are sorted. In other words, if we sort the booths by coordinate, we can efficiently compute the “sum of attraction powers of booths to the right within distance \(D\),” allowing us to calculate the contribution from booth \(i\) all at once.

To efficiently compute this “range sum,” we use a prefix sum. Additionally, to find the position of the farthest booth to the right within distance \(D\) from booth \(i\), it is efficient to use binary search (bisect).

Algorithm

1. Sort all booths in ascending order of coordinate \(X_i\).
2. Precompute a prefix sum array prefix_sum of the attraction powers \(S_i\).
3. For each booth \(i\):
   • Let \(x_i\) be its coordinate.
   • Use binary search to find the largest \(j\) satisfying \(x_j \leq x_i + D\).
   • Compute the sum of attraction powers in this range using the prefix sum.
   • Add \(S_i\) multiplied by that sum to the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • For each booth, binary search and prefix sum lookup take \(O(\log N + 1) = O(\log N)\), giving \(O(N \log N)\) overall
• Space complexity: \(O(N)\)
  • \(O(N)\) is needed for the coordinate/attraction power lists and the prefix sum array

Implementation Notes

• Booths must be sorted by coordinate first.

• Prefix sums are essential for efficiently computing range sums.

• bisect.bisect_right(X, x_i + D) returns “the first index exceeding \(x_i + D\),” so the index of the last element actually within the range requires subtracting 1.

• To avoid pairing a booth with itself, check the condition right > i.

  Source Code

import bisect

N, D = map(int, input().split())
XS = [tuple(map(int, input().split())) for _ in range(N)]

# 座標でソート
XS.sort()

X = [x for x, s in XS]
S = [s for x, s in XS]

# 累積和を前計算
prefix_sum = [0] * (N + 1)
for i in range(N):
    prefix_sum[i + 1] = prefix_sum[i] + S[i]

result = 0
for i in range(N):
    x_i, s_i = XS[i]
    # |X_j - X_i| <= D となる j を探す → X_j <= X_i + D
    right = bisect.bisect_right(X, x_i + D) - 1
    if right > i:
        # Σ_{j=i+1}^{right} S_j を計算
        sum_s = prefix_sum[right + 1] - prefix_sum[i + 1]
        result += s_i * sum_s

print(result)

---

This editorial was generated by qwen3-coder-480b.