Overview

This problem asks us to find the nearest post office from each of Takahashi’s and Aoki’s positions, then calculate the total number of registered users after they register.

Analysis

Key Observations

1. We need to efficiently find the nearest post office: Since there can be up to \(2 \times 10^5\) post offices, a naive approach of calculating distances to all post offices for each person in \(O(N)\) would work, but using binary search we can find it in \(O(\log N)\).

2. Be careful when both register at the same post office: If both people register at the same post office, we count that post office’s registered users only once (but with +2 added for both people).

3. Tiebreaker when multiple post offices are equally close: When distances are equal, we choose the one with the smallest coordinate.

Issues with the Naive Approach

While a brute force \(O(N)\) approach works for this problem, if the number of post offices increases further or if there are multiple queries, a more efficient method would be needed.

Algorithm

1. Sort post offices by coordinate

By sorting post offices in ascending order of coordinates, we can use binary search.

2. Find the nearest post office using binary search

To find the nearest post office for position \(pos\):

1. Use bisect_left to find the position \(idx\) where \(pos\) would be inserted
2. If \(idx = 0\): All post offices are to the right of \(pos\), so the leftmost post office (index 0) is nearest
3. If \(idx = N\): All post offices are to the left of \(pos\), so the rightmost post office (index \(N-1\)) is nearest
4. Otherwise: Compare the two neighbors, left \(xs[idx-1]\) and right \(xs[idx]\)
   • If distance to left \(\leq\) distance to right, choose left (prioritize smaller coordinate)
   • Otherwise, choose right

Concrete example: Post offices at coordinates \([1, 5, 10]\) with \(pos = 7\) - bisect_left gives \(idx = 2\) (7 is between 5 and 10) - Distance to left: \(7 - 5 = 2\) - Distance to right: \(10 - 7 = 3\) - Since \(2 < 3\), the post office at coordinate 5 (index 1) is nearest

3. Calculate the result

• If both register at the same post office → original registered users at that post office \(+ 2\)
• If they register at different post offices → (Takahashi’s post office users \(+ 1\)) \(+\) (Aoki’s post office users \(+ 1\))

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(\log N)\) × 2 for binary search
• Space complexity: \(O(N)\)
  • List to store post office information

Implementation Notes

1. Implementing the tiebreaker: To choose the smaller coordinate when distances are equal, use the condition dist_left <= dist_right to naturally achieve this (the position of the equals sign is key).

2. Handling boundary conditions: When the result of bisect_left is 0 or \(N\), handle these cases separately first to avoid out-of-bounds array access.

3. Checking if it’s the same post office: This can be easily determined by comparing indices.

Source Code

import bisect

def solve():
    N, P, Q = map(int, input().split())
    
    posts = []
    for _ in range(N):
        x, c = map(int, input().split())
        posts.append((x, c))
    
    # Sort by coordinate
    posts.sort()
    
    xs = [p[0] for p in posts]
    
    def find_nearest(pos):
        # Find the post office nearest to pos
        # If there are multiple, choose the one with the smallest coordinate
        idx = bisect.bisect_left(xs, pos)
        
        if idx == 0:
            return 0
        elif idx == N:
            return N - 1
        else:
            # xs[idx-1] < pos <= xs[idx] or xs[idx-1] <= pos < xs[idx]
            dist_left = pos - xs[idx - 1]
            dist_right = xs[idx] - pos
            
            if dist_left <= dist_right:
                return idx - 1
            else:
                return idx
    
    idx_p = find_nearest(P)
    idx_q = find_nearest(Q)
    
    if idx_p == idx_q:
        # Register at the same post office
        result = posts[idx_p][1] + 2
    else:
        # Register at different post offices
        result = (posts[idx_p][1] + 1) + (posts[idx_q][1] + 1)
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.