Overview

This is a problem where, for each house, we need to find the distance to the nearest shelter. By leveraging the fact that the shelter coordinates are sorted, we can efficiently find the nearest shelter using binary search.

Analysis

Naive Approach and Its Issues

The simplest method is, for each house \(i\), to compute the distance \(|X_i - P_j|\) to every shelter \(j\) and find the minimum. However, this method takes \(O(N \times M)\) time. Since \(N, M\) can be up to \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) computations in the worst case, which will not fit within the time limit (TLE).

Key Insight

The shelter coordinates \(P\) are given sorted in ascending order. The operation of finding “the element closest to a given value” in a sorted array can be accomplished in \(O(\log M)\) using binary search.

Understanding Through a Concrete Example

For example, consider a house at coordinate \(x = 5\) with shelter coordinates \(P = [1, 3, 7, 10]\).

Using binary search to find the “insertion position” of \(x = 5\), we get \(\text{idx} = 2\) (just before \(P[2] = 7\)). At this point, the candidates for the nearest shelter are:

• Right candidate: \(P[\text{idx}] = P[2] = 7\) (distance \(= 7 - 5 = 2\))
• Left candidate: \(P[\text{idx} - 1] = P[1] = 3\) (distance \(= 5 - 3 = 2\))

Therefore, the distance to the nearest shelter is \(\min(2, 2) = 2\).

Algorithm

1. For each house coordinate \(x\), use bisect_left on the shelter coordinate array \(P\) to find the insertion position \(\text{idx}\).
2. \(\text{idx}\) represents “the index of the first element in \(P\) that is greater than or equal to \(x\).”
3. The nearest shelter is the closer of the following up to 2 candidates:
   • \(P[\text{idx}]\) (the smallest shelter coordinate \(\geq x\); exists only if \(\text{idx} < M\))
   • \(P[\text{idx} - 1]\) (the largest shelter coordinate \(< x\); exists only if \(\text{idx} > 0\))
4. Compare the distances to both candidates and take the smaller one as the answer.

Complexity

• Time complexity: \(O(N \log M)\)
  • One binary search is performed per house, each taking \(O(\log M)\), for a total of \(O(N \log M)\)
• Space complexity: \(O(N + M)\)
  • For storing the input arrays and the output array

Implementation Notes

• Boundary checks: When the insertion position \(\text{idx}\) is \(0\) (all shelters are to the right of the house) or \(M\) (all shelters are to the left of the house), care must be taken to avoid out-of-bounds array access.

• Output optimization: In Python, calling print \(N\) times is slow, so we accumulate results in a list and output them all at once using '\n'.join(out).

• Meaning of bisect_left: bisect_left(P, x) returns the leftmost position where \(x\) can be inserted into the sorted array \(P\) while maintaining sorted order. In other words, \(P[\text{idx}-1] < x \leq P[\text{idx}]\) holds (when the boundaries exist).

  Source Code

import bisect

def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    out = []
    for x in X:
        idx = bisect.bisect_left(P, x)
        best = float('inf')
        if idx < M:
            best = min(best, P[idx] - x)
        if idx > 0:
            best = min(best, x - P[idx - 1])
        out.append(str(best))
    
    print('\n'.join(out))

main()

---

This editorial was generated by claude4.6opus-thinking.