Overview

For pairs of booths \((i,j)\) whose coordinate difference is at most \(D\), we want to find the total sum of synergy effects \(S_i \times S_j\). We sort by coordinate and use the two-pointer (sliding window) technique to efficiently compute the sum while maintaining the “set of nearby booths.”

Analysis

What we want to compute is [ \sum_{1\le i\le N,\ |X_i-X_j|\le D} S_iS_j ]

Why the Naive Solution Doesn’t Work

Checking all pairs takes \(O(N^2)\), and with \(N\le 2\times 10^5\), this results in up to approximately \(2\times 10^{10}\) pairs, which won’t finish in time (TLE).

Key Observation

• All \(X_i\) are distinct and lie on a single line, so sorting by coordinate in ascending order makes the distance condition easy to handle.
• After sorting, when considering a booth \(j\) as the right endpoint, the condition \(|X_i-X_j|\le D\) (for \(i<j\)) simplifies to just [ X_j - X_i \le D ] which forms a contiguous interval on the left side that satisfies the condition.

How to Solve It

As we move the right endpoint \(j\) from left to right: - Advance the smallest left endpoint \(left\) to maintain the condition (two-pointer technique) - Maintain \(sum\_s\), the sum of attractiveness values of booths in the interval \([left,\,j-1]\)

Then the total synergy effect for all partners that can pair with booth \(j\) is [ Sj \times \sum{i=left}^{j-1} S_i = S_j \times sum_s ] which can be added in one step.

(Example) If \(S_j=5\) and the nearby \(S\) values on the left are \(2,3,4\), then the synergy is \(5\times2+5\times3+5\times4=5\times(2+3+4)\).

Algorithm

1. Sort the input \((X_i,S_i)\) in ascending order of \(X\).
2. Prepare two pointers \(left, right\) and \(sum\_s\), the sum of attractiveness values in the current valid interval (the set of booths to the left of \(right\) that satisfy the distance condition).
3. Process \(right=0..N-1\) in order:
   • While \(X_{right} - X_{left} > D\), move \(left\) to the right and subtract the excluded booth’s \(S\) from \(sum\_s\).
   • At this point, \(left..right-1\) contains all booths “within distance \(D\) from \(right\).”
   • Add \(S_{right} \times sum\_s\) to the answer (accounting for all pairs involving \(right\)).
   • Add \(S_{right}\) to \(sum\_s\) to prepare for the next \(right\).
4. Output the final answer.

In this method, each booth enters and leaves the interval at most once due to \(left/right\), so the scanning part runs in \(O(N)\).

Complexity

• Time complexity: Sorting is \(O(N\log N)\), the two-pointer scan is \(O(N)\), so the overall complexity is \(O(N\log N)\)
• Space complexity: \(O(N)\) for storing the input arrays

Implementation Notes

• Always sort by coordinate before applying the two-pointer technique (this ensures that “partners satisfying the condition form a contiguous interval”).

• \(sum\_s\) must always correctly reflect “the sum of \(S\) values in the current valid interval” (subtract when moving the left endpoint / add when including the right endpoint).

• The answer is guaranteed to be at most \(2^{63}-1\). Python’s int supports arbitrary precision, so it’s safe as-is (in other languages, use 64-bit integers).

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.