Overview

Given the coordinates and popularity values of booths, the problem asks to find the sum of products of popularity values for all booth pairs whose coordinate difference is at most \(D\).

Analysis

A naive approach would check all booth pairs \((i, j)\) to determine whether \(|X_i - X_j| \leq D\), and sum up \(S_i \times S_j\) for pairs satisfying the condition. However, this method has a time complexity of \(O(N^2)\), and since \(N\) can be as large as \(2 \times 10^5\), it will not fit within the time limit.

To solve this efficiently, we can sort the booths by coordinate and use the two-pointer (sliding window) technique to manage booths within the valid range while computing the answer. This allows us to quickly find the leftmost booth satisfying the condition for each booth.

Algorithm

1. Sort the booths in ascending order of coordinate \(X_i\).
2. Initialize the left index left to 0 and the cumulative sum prefix_sum to 0.
3. Move the right index right from 0 to \(N-1\) in order:
   • While the difference in coordinates between the current booth points[right] and the leftmost booth points[left] is greater than \(D\), advance left while subtracting the corresponding popularity value from prefix_sum.
   • Add the product of the current booth’s popularity and the sum of popularity values of booths currently in the range (prefix_sum) to the total total.
   • Add the current booth’s popularity to prefix_sum.

In this method, for each booth j, we efficiently compute the sum of popularity values of booths i satisfying the condition (\(i < j\) and \(X_j - X_i \leq D\)), and calculate \(S_j \times (\sum S_i)\).

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, \(O(N)\) for the two-pointer processing)
• Space complexity: \(O(N)\) (arrays to store booth information)

Implementation Notes

• The booths need to be sorted by coordinate.

• In the two-pointer technique, the left index left is adjusted according to the condition while maintaining the sum of popularity values within the current range.

• Be careful about the timing of updating prefix_sum (compute the product before adding the current booth’s popularity).

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    D = int(data[1])
    points = []
    index = 2
    for i in range(n):
        x = int(data[index])
        s = int(data[index+1])
        index += 2
        points.append((x, s))
    
    points.sort()
    total = 0
    prefix_sum = 0
    left = 0
    for right in range(n):
        while points[right][0] - points[left][0] > D:
            prefix_sum -= points[left][1]
            left += 1
        total += points[right][1] * prefix_sum
        prefix_sum += points[right][1]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.