Overview

Given booths arranged on a straight line, for all pairs \((i, j)\) where the difference in coordinates is at most \(D\), we need to efficiently compute the sum of products of attractiveness values \(S_i \times S_j\).

Analysis

Naive Approach and Its Issues

The simplest method is to enumerate all pairs \((i, j)\) (\(i < j\)), check whether \(|X_i - X_j| \leq D\), and add the product. However, the number of pairs can be up to \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\), which would result in TLE (Time Limit Exceeded).

Key Insight

We can speed things up by combining sorting and binary search.

If we sort the booths in ascending order of coordinates, then for booth \(i\), the booths \(j\) (\(j > i\)) that can collaborate with it form a contiguous range satisfying \(X[j] \leq X[i] + D\). The right endpoint of this range can be found in \(O(\log N)\) using binary search.

Furthermore, the desired value can be transformed as follows:

\[\sum_{\text{valid } (i,j)} S_i \times S_j = \sum_{i} S_i \times \left( \sum_{j=i+1}^{r_i} S_j \right)\]

Here, \(r_i\) is the index of the rightmost booth that can collaborate with booth \(i\). The inner sum (the range sum of \(S_j\)) can be computed in \(O(1)\) using a prefix sum.

Concrete Example

For example, suppose the booths after sorting are as follows (\(D = 3\)):

Index	Coordinate \(X\)	Attractiveness \(S\)
0	1	2
1	3	5
2	4	3
3	8	1

• \(i=0\): \(X[j] \leq 1+3=4\), so \(j=1,2\) are eligible → \(S[0] \times (S[1]+S[2]) = 2 \times 8 = 16\)
• \(i=1\): \(X[j] \leq 3+3=6\), so \(j=2\) is eligible → \(S[1] \times S[2] = 5 \times 3 = 15\)
• \(i=2\): \(X[j] \leq 4+3=7\), so no eligible booths → \(0\)

The total sum is \(16 + 15 = 31\).

Algorithm

1. Sort the booths in ascending order of coordinate \(X_i\).
2. Build a prefix sum array prefix_S for the attractiveness values \(S\).
3. For each booth \(i\) (\(0 \leq i < N\)):
   • Use binary search to find the maximum \(j\) satisfying \(X[j] \leq X[i] + D\) (using bisect_right).
   • Use the prefix sum to retrieve \(S[i+1] + S[i+2] + \cdots + S[r_i]\) in \(O(1)\).
   • Add \(S[i] \times (\text{range sum})\) to the answer.
4. Output the total sum.

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting, and \(O(\log N)\) for binary search per booth (totaling \(O(N \log N)\))
• Space complexity: \(O(N)\)
  • Used for storing coordinate/attractiveness arrays and the prefix sum array

Implementation Notes

• After sorting, coordinates are in ascending order, so \(|X_i - X_j| = X_j - X_i\) (\(j > i\)) and the absolute value can be removed.

• bisect_right(X, X[i] + D) returns “the first position greater than \(X[i] + D\)”, so subtract \(1\) to get the rightmost index.

• The answer can become very large, but Python natively supports arbitrary-precision integers, so there is no concern about overflow.

• Since the input can be very large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    booths = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        booths.append((x, s))
    
    # Sort by coordinate
    booths.sort()
    
    X = [b[0] for b in booths]
    S = [b[1] for b in booths]
    
    # For each booth i, find all booths j > i such that X[j] - X[i] <= D
    # Since sorted, X[j] >= X[i], so condition is X[j] <= X[i] + D
    
    # We need sum over all valid pairs (i,j) of S[i]*S[j]
    # = sum_i S[i] * (sum of S[j] for j in range where i < j and X[j] <= X[i]+D)
    
    # Use prefix sums of S
    prefix_S = [0] * (N + 1)
    for i in range(N):
        prefix_S[i + 1] = prefix_S[i] + S[i]
    
    total = 0
    for i in range(N):
        # Find rightmost j such that X[j] <= X[i] + D
        right = bisect_right(X, X[i] + D) - 1
        # Sum S[j] for j from i+1 to right
        if right > i:
            sum_s = prefix_S[right + 1] - prefix_S[i + 1]
            total += S[i] * sum_s
    
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.