Overview

Given the positions of houses and shelters, the problem asks to find the distance from each house to its nearest shelter.

Analysis

To find the nearest shelter for each house, naively computing the distance to every shelter would take \(O(N \times M)\) time. Since \(N, M\) can be up to \(2 \times 10^5\), this would require \(4 \times 10^{10}\) computations, which exceeds the time limit.

However, there is an important property: both the house coordinates \(X_i\) and the shelter coordinates \(P_j\) are sorted. By leveraging this property, we can efficiently find the nearest shelter using binary search.

Algorithm

1. Read the house coordinate list \(X\) and the shelter coordinate list \(P\) as input.
2. For each house \(x\), use binary search (bisect_left) to find the position \(idx\) where \(x\) would be inserted in \(P\).
3. Based on the found position \(idx\), handle the following three cases:
   • If \(idx = 0\): There is no shelter to the left of \(x\), so compute the distance to the first shelter \(P[0]\).
   • If \(idx = len(P)\): There is no shelter to the right of \(x\), so compute the distance to the last shelter \(P[-1]\).
   • Otherwise: Compute the distances to the two shelters \(P[idx-1]\) and \(P[idx]\) on either side of \(x\), and take the smaller one.
4. Append the computed result to an output list, and print everything at once at the end.

Complexity

• Time complexity: \(O(N \log M)\)
  • A binary search is performed for each house, so each of the \(N\) searches takes \(O(\log M)\) time.
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the house coordinate list \(X\) and the shelter coordinate list \(P\).

Implementation Notes

• By using Python’s standard library bisect, binary search can be implemented efficiently.

• Care must be taken to properly handle boundary conditions (the first and last elements).

• Output can be sped up by collecting results as a string and printing them all at once.

  Source Code

import bisect

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    X = list(map(int, data[2:2+n]))
    P = list(map(int, data[2+n:2+n+m]))
    
    res = []
    for x in X:
        idx = bisect.bisect_left(P, x)
        if idx == 0:
            d = P[0] - x
        elif idx == len(P):
            d = x - P[-1]
        else:
            d1 = x - P[idx-1]
            d2 = P[idx] - x
            d = min(d1, d2)
        res.append(str(d))
    
    print("\n".join(res))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.