Overview

On a number line with \(N\) post offices, two residents (Takahashi and Aoki) each choose the post office closest to them. The problem asks to find the total number of users at the relevant post offices after both have registered.

Analysis

Since the number of post offices \(N\) can be as large as \(2 \times 10^5\), checking all \(N\) post offices for each person to calculate distances (linear search) takes \(O(N)\) time overall. Since there are only 2 people this time, a linear search would be fast enough, but to more efficiently find the “closest element,” it is common to use binary search.

To perform binary search, the post office data must be sorted in ascending order of coordinates \(X_i\).

How to Find the Nearest Post Office

The post office closest to a given coordinate \(pos\) in the sorted list is one of the following: 1. The smallest coordinate that is greater than or equal to \(pos\) (the position idx found by bisect_left) 2. The largest coordinate that is less than \(pos\) (the position idx - 1)

We compare the distances of these two candidates. According to the problem statement, “if the distances are equal, choose the one with the smaller coordinate,” so when distances are equal, we implement it to select idx - 1.

Calculating the Total Number of Users

Let t_idx be the index of the post office chosen by Takahashi, and a_idx be the one chosen by Aoki. - If both choose the same post office (t_idx == a_idx): The original number of users \(C_{t\_idx}\) at that post office plus the 2 registrations gives \(C_{t\_idx} + 2\). - If they choose different post offices (t_idx != a_idx): Each post office gets one additional registration, so the total is \((C_{t\_idx} + 1) + (C_{a\_idx} + 1)\).

Algorithm

1. Read the post office information and sort it in ascending order by coordinate \(X_i\).
2. Use binary search (the bisect module in Python) to find the index of the post office closest to Takahashi’s coordinate \(P\) and Aoki’s coordinate \(Q\).
   • Use bisect_left on the coordinate list xs to obtain the insertion position idx.
   • Choose the one among xs[idx] and xs[idx-1] that is closer to \(pos\) and satisfies the conditions.
3. Based on the identified indices, apply conditional branching and output the final total number of users.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the post offices takes \(O(N \log N)\).
  • Binary search is \(O(\log N)\), and performing it for 2 people is still \(O(\log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the post office information.

Implementation Notes

• Binary search boundaries: Care must be taken when the index returned by bisect_left is 0 (all post offices are to the right) or N (all post offices are to the left), and the processing must be handled accordingly.

• Fast I/O: Since \(N\) can be large, in Python, using sys.stdin.read().split() to read all input at once can reduce execution time.

• Checking for the same post office: By comparing indices (or coordinates), we can accurately determine whether both people chose the same post office.

  Source Code

import sys
import bisect

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリスト化します。
    # N=2*10^5 程度の入力であれば、この方法がPythonにおいて高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 郵便局の数, P: 高橋君の座標, Q: 青木君の座標
    N = int(input_data[0])
    P = int(input_data[1])
    Q = int(input_data[2])
    
    # 郵便局の情報 (座標 X, 利用者数 C) を格納します。
    offices = []
    for i in range(N):
        x = int(input_data[3 + 2 * i])
        c = int(input_data[4 + 2 * i])
        offices.append((x, c))
    
    # 座標順にソートすることで、二分探索を利用可能にします。
    offices.sort()
    
    # 二分探索用に座標のみのリストを作成します。
    xs = [o[0] for o in offices]
    
    def find_nearest_index(pos):
        """
        指定された座標 pos から最も近い郵便局のインデックスを返します。
        距離が同じ場合は、座標が小さい方を選択します。
        """
        # bisect_left は pos を挿入すべき位置（xs[idx] >= pos となる最小の idx）を返します。
        idx = bisect.bisect_left(xs, pos)
        
        # pos がすべての郵便局の座標より小さい場合
        if idx == 0:
            return 0
        # pos がすべての郵便局の座標より大きい場合
        if idx == N:
            return N - 1
        
        # 候補は xs[idx-1] と xs[idx] の2つです。
        dist_left = abs(pos - xs[idx - 1])
        dist_right = abs(xs[idx] - pos)
        
        # 最も近いものを選び、距離が同じなら座標が小さい方 (idx-1) を選びます。
        if dist_left <= dist_right:
            return idx - 1
        else:
            return idx
    
    # 高橋君と青木君がそれぞれ選ぶ郵便局のインデックスを求めます。
    t_idx = find_nearest_index(P)
    a_idx = find_nearest_index(Q)
    
    if t_idx == a_idx:
        # 二人が同じ郵便局に登録した場合
        # その郵便局の登録者数は元の人数に二人分（+2）を加えたものになります。
        print(offices[t_idx][1] + 2)
    else:
        # 二人が異なる郵便局に登録した場合
        # それぞれの郵便局の登録者数を1人ずつ増やした後の合計を求めます。
        print((offices[t_idx][1] + 1) + (offices[a_idx][1] + 1))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.