Overview

Given \(N\) houses arranged on a number line, the problem asks to find, for each house, the distance to the nearest shelter (out of \(M\) shelters in total).

Analysis

Naive Approach

A straightforward approach would be, for each house, to compute the distance to every shelter and find the minimum. However, this requires \(M\) comparisons per house, resulting in an overall time complexity of \(O(N \times M)\). Since \(N, M \leq 2 \times 10^5\) in this problem, this would require up to approximately \(4 \times 10^{10}\) computations, which will not fit within the time limit (resulting in TLE).

Efficient Approach

We take advantage of the fact that the shelter coordinates \(P_1, P_2, \ldots, P_M\) are sorted in ascending order. For a given house \(X_i\), the nearest shelter is either “the leftmost shelter with a coordinate greater than or equal to \(X_i\)” or “the rightmost shelter with a coordinate less than \(X_i\)”.

For example, if shelters are located at coordinates \(10, 40, 70\) and a house is at coordinate \(50\), the nearest candidates are either \(40\) or \(70\).

To find “the position where a specific value should be inserted in a sorted array,” we can use binary search, which allows us to find the candidates in \(O(\log M)\) per house.

Algorithm

1. For each house \(X_i\), repeat the following steps.
2. Using binary search (the bisect_left function in Python), find the index idx at which the first value greater than or equal to \(X_i\) appears in the shelter list \(P\).
3. Depending on the value of idx, compute the distance by considering the following 3 cases:
   • When idx == 0: All shelters are to the right of the house. The nearest one is \(P[0]\).
   • When idx == M: All shelters are to the left of the house. The nearest one is \(P[M-1]\).
   • Otherwise: There are two candidates: \(P[idx]\) immediately to the right of the house and \(P[idx-1]\) immediately to the left. Compute the distance to both and take the smaller one.
4. Output the results for all houses in order.

Complexity

• Time complexity: \(O(N \log M)\)
  • For each house (\(N\) houses), we perform a binary search on the shelter list (of size \(M\)).
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the coordinates of the houses and shelters.

Implementation Notes

• Using binary search: By using bisect_left from Python’s standard library bisect module, the search can be performed concisely and efficiently.

• Fast I/O: Since \(N, M\) can be large, using sys.stdin.read instead of input(), and collecting results into a list to output all at once with join, helps reduce time lost to I/O operations.

• Handling boundary conditions: Care must be taken not to access out-of-bounds array indices when a house is located outside the range of shelters (to the left of the leftmost shelter or to the right of the rightmost shelter).

  Source Code

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    X = list(map(int, input_data[2 : 2 + N]))
    P = list(map(int, input_data[2 + N : 2 + N + M]))
    
    results = []
    for x in X:
        idx = bisect_left(P, x)
        
        if idx == 0:
            results.append(P[0] - x)
        elif idx == M:
            results.append(x - P[M-1])
        else:
            dist_right = P[idx] - x
            dist_left = x - P[idx-1]
            if dist_right < dist_left:
                results.append(dist_right)
            else:
                results.append(dist_left)
    
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    main()

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