Overview

This problem asks us to find the total number of users at the two post offices where Takahashi and Aoki each register at their nearest post office. However, we need to be careful not to double-count when they register at the same post office.

Analysis

In this problem, we first need to find the nearest post office for each person. A naive approach would be to calculate the distance to every post office and select the minimum, but since the number of post offices \(N\) can be up to \(2 \times 10^5\), a brute-force search each time would have \(O(N)\) time complexity, resulting in \(O(N)\) overall, which would cause TLE.

Instead, by sorting the post offices by coordinate, we can efficiently find the nearest post office using binary search. Specifically, using bisect.bisect_left to check the candidates on the left and right of the person’s coordinate is sufficient.

Furthermore, if both people choose the same post office, the number of registered users only increases by 2, and we need to treat the total as the user count of a single post office. In other words, if they register at different post offices, we add 1 to each post office’s user count and sum them up; if they register at the same post office, we output the value with 2 added to that single post office’s user count.

Algorithm

1. Read the post office information as \((X_i, C_i)\) and sort in ascending order of coordinate \(X_i\).
2. For each of Takahashi’s coordinate \(P\) and Aoki’s coordinate \(Q\), find the nearest post office as follows:
   • Use bisect_left to find the insertion position in the sorted coordinate list.
   • Among the candidates around that position (up to 3), compare distances and select the closest one (if distances are equal, choose the one with the smaller coordinate).
3. Determine whether the two people chose the same post office:
   • If the same, output the post office’s user count plus 2.
   • If different, output the sum of each post office’s user count plus 1.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\)

Implementation Notes

• Sort the post office information as pairs \((X_i, C_i)\).

• By using bisect_left for searching, we can narrow down the candidates to at most 3.

• When both register at the same post office, note that we only increase the user count by 2 (since it’s the same object, we must not double-count).

  Source Code

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = int(data[1])
    Q = int(data[2])
    
    X = []
    C = []
    for i in range(N):
        x = int(data[3 + 2*i])
        c = int(data[4 + 2*i])
        X.append(x)
        C.append(c)
    
    # 座標でソート
    sorted_pairs = sorted(zip(X, C))
    X_sorted = [x for x, c in sorted_pairs]
    C_sorted = [c for x, c in sorted_pairs]
    
    # 最寄りの郵便局を探す関数
    def find_nearest(x):
        pos = bisect.bisect_left(X_sorted, x)
        candidates = []
        if pos < N:
            candidates.append((abs(X_sorted[pos] - x), X_sorted[pos], C_sorted[pos]))
        if pos > 0:
            candidates.append((abs(X_sorted[pos-1] - x), X_sorted[pos-1], C_sorted[pos-1]))
        if pos < N-1:
            candidates.append((abs(X_sorted[pos+1] - x), X_sorted[pos+1], C_sorted[pos+1]))
        
        # 距離でソートし、距離が同じなら座標が小さい方
        candidates.sort(key=lambda t: (t[0], t[1]))
        return candidates[0][1], candidates[0][2]
    
    Px, Pc = find_nearest(P)
    Qx, Qc = find_nearest(Q)
    
    if Px == Qx:
        total = Pc + Qc + 2 if Px != P or Qx != Q else Pc + Qc + 2  # どちらも新規登録なので+2
        # 実際には、元の登録者数 + 高橋君 + 青木君 の合計が Pc+2 や Qc+2 ではなく、
        # 登録後の人数は Pc+1 と Qc+1 （同じ局ならどちらも同じオブジェクト）
        # 同じ局なら、最終的な登録者数は元の人数 + 2 （高橋君と青木君）
        total = Pc + 2
    else:
        total = (Pc + 1) + (Qc + 1)
    
    print(total)

if __name__ == "__main__":
    main()

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