概要

郵便局の座標をソートし、各人の住居位置 \(P, Q\) に対して「最寄りの郵便局」を二分探索で求め、登録後の利用者数（+1ずつ）を合計します。

考察

• 各人は「距離が最小」の郵便局を選び、同距離なら「座標が小さい方」を選びます。
• 素朴に、各人について全ての郵便局との距離を調べると \(O(N)\) で最寄りが求まりますが、今回 \(N \le 2 \times 10^5\) なので（2人分とはいえ）十分間に合います。
  ただし、競技プログラミングとしては「最寄り問題はソート＋二分探索で一般に高速化できる」という典型を押さえるのが重要です（人が増える設定でも拡張しやすい）。
• 1次元（一直線）上では、座標をソートしておけば、ある位置 pos の最寄り候補は
  • pos 以上で最初に現れる郵便局（右側候補）
  • その1つ左の郵便局（左側候補） の高々2つに絞れます。なぜなら、ソート済み配列ではそれより遠い点は必ず距離が大きくなるためです。
• 同距離のときは座標が小さい郵便局を選ぶ必要があります。
  これは「左候補と右候補の距離が等しいなら左を採用」とすれば、そのままタイブレーク条件（座標が小さい方）を満たします。
• 最後の合計は少し注意が必要で、二人が別の郵便局なら
  • \((C_{ip}+1) + (C_{iq}+1) = C_{ip} + C_{iq} + 2\) 二人が同じ郵便局なら
  • \(C_{i}+2\) を1回だけ数えます。

アルゴリズム

1. 郵便局データ \((X_i, C_i)\) を \(X_i\) で昇順ソートする。
2. ソート後の座標配列 xs を作る。
3. bisect_left(xs, pos) で pos を挿入できる位置 i を求める。
   • i = 0 なら最寄りは先頭
   • i = N なら最寄りは末尾
   • それ以外なら左候補 i-1 と右候補 i の距離を比較し、
     \(|pos-xs[i-1]| \le |xs[i]-pos|\) なら左、そうでなければ右を選ぶ
     （\(\le\) により同距離なら左＝座標が小さい方を選べる）
4. 上を \(P, Q\) それぞれに対して行い、最寄り郵便局のインデックス ip, iq を得る。
5. ip == iq なら答えは cs[ip] + 2、違うなら cs[ip] + cs[iq] + 2 を出力する。

（例）xs = [0, 10], pos = 5 のとき
左距離 \(|5-0|=5\)、右距離 \(|10-5|=5\) で同距離なので左（座標0）を選びます。

計算量

• 時間計算量: ソートが \(O(N \log N)\)、二分探索は2回で \(O(\log N)\) なので合計 \(O(N \log N)\)
• 空間計算量: 配列保持に \(O(N)\)

実装のポイント

• bisect_left の戻り値 i は「xs[i] >= pos となる最小の i」です。端（i=0 や i=N）の処理を忘れないようにします。

• タイブレーク（同距離なら座標が小さい方）を満たすには、距離比較を dl <= dr として左を優先します。

• 最終出力は「登録後」なので、二人分で必ず +2 が入ります。ただし同じ郵便局ならその郵便局の人数を1回だけ数える（C + 2）点に注意します。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。