Overview

Sort the coordinates of the post offices, and for each person’s residence position \(P, Q\), find the “nearest post office” using binary search, then sum up the number of users after registration (+1 each).

Analysis

• Each person chooses the post office with the “minimum distance,” and if distances are equal, they choose the one with the “smaller coordinate.”
• Naively, checking the distance to all post offices for each person finds the nearest in \(O(N)\), and since \(N \le 2 \times 10^5\) (even for two people), this is fast enough.
  However, for competitive programming, it’s important to know the typical technique that “nearest point problems can generally be sped up with sorting + binary search” (this also scales easily if the number of people increases).
• On a 1-dimensional line (a straight line), if the coordinates are sorted, the nearest candidates for a position pos are narrowed down to at most two:
  • The first post office appearing at or after pos (right candidate)
  • The post office one position to its left (left candidate) This is because in a sorted array, any point farther away necessarily has a greater distance.
• When distances are equal, we need to choose the post office with the smaller coordinate.
  This is handled by “if the left candidate and right candidate have equal distances, adopt the left one,” which directly satisfies the tiebreak condition (smaller coordinate).
• The final summation requires some care: if the two people choose different post offices, the answer is
  • \((C_{ip}+1) + (C_{iq}+1) = C_{ip} + C_{iq} + 2\) If the two people choose the same post office, the answer is
  • \(C_{i}+2\) counted only once.

Algorithm

1. Sort the post office data \((X_i, C_i)\) in ascending order by \(X_i\).
2. Create the sorted coordinate array xs.
3. Use bisect_left(xs, pos) to find the insertion position i for pos.
   • If i = 0, the nearest is the first element.
   • If i = N, the nearest is the last element.
   • Otherwise, compare the distances of the left candidate i-1 and the right candidate i:
     If \(|pos - xs[i-1]| \le |xs[i] - pos|\), choose the left; otherwise, choose the right.
     (The \(\le\) ensures that when distances are equal, the left = smaller coordinate is chosen.)
4. Perform the above for both \(P\) and \(Q\) to obtain the nearest post office indices ip, iq.
5. If ip == iq, output cs[ip] + 2; otherwise, output cs[ip] + cs[iq] + 2.

(Example) When xs = [0, 10] and pos = 5:
Left distance \(|5-0|=5\), right distance \(|10-5|=5\) — distances are equal, so choose the left (coordinate 0).

Complexity

• Time complexity: Sorting is \(O(N \log N)\), binary search is performed twice at \(O(\log N)\) each, so the total is \(O(N \log N)\).
• Space complexity: \(O(N)\) for storing the arrays.

Implementation Notes

• The return value i of bisect_left is “the smallest i such that xs[i] >= pos.” Be careful not to forget handling the boundary cases (i=0 and i=N).

• To satisfy the tiebreak (choose the smaller coordinate when distances are equal), use dl <= dr in the distance comparison to prioritize the left candidate.

• The final output is “after registration,” so a total of +2 is always added for the two people. However, note that if they choose the same post office, that post office’s count is counted only once (C + 2).

  Source Code

import sys
import bisect

def nearest_index(xs, pos):
    i = bisect.bisect_left(xs, pos)
    if i == 0:
        return 0
    if i == len(xs):
        return len(xs) - 1
    left = i - 1
    right = i
    dl = abs(pos - xs[left])
    dr = abs(xs[right] - pos)
    if dl <= dr:
        return left
    else:
        return right

def main():
    input = sys.stdin.readline
    N, P, Q = map(int, input().split())
    offices = [tuple(map(int, input().split())) for _ in range(N)]
    offices.sort()
    xs = [x for x, _ in offices]
    cs = [c for _, c in offices]

    ip = nearest_index(xs, P)
    iq = nearest_index(xs, Q)

    if ip == iq:
        ans = cs[ip] + 2
    else:
        ans = cs[ip] + cs[iq] + 2

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.