Overview

We exploit the fact that both houses and shelters are sorted in coordinate order, efficiently finding the “distance to the nearest shelter” for each house.

Analysis

The most naive approach would be, for each house \(X_i\), to examine all shelters \(P_j\) and compute \(\min_j |X_i-P_j|\). However, this is \(O(NM)\), which can be as large as \((2\times 10^5)^2\), resulting in a guaranteed TLE.

The key observations are the following two points:

• The house coordinates \(X_1<X_2<\cdots<X_N\) and the shelter coordinates \(P_1<P_2<\cdots<P_M\) are both already sorted in ascending order.
• As we scan houses from left to right, the “index of the nearest shelter” never moves back to the left — it either stays the same or moves to the right (monotonicity).

Intuitively, as a house moves to the right, shelters on the right side tend to become more favorable, and a shelter on the left that was already determined to be “not close” will never suddenly become optimal.
Thanks to this monotonicity, we can process all houses by simply advancing the shelter pointer in one direction.

Example: If the shelters are \(P=[2,10,20]\), as houses progress rightward through \(x=1,5,12,19\), the nearest shelters are \(2,2,10,20\) respectively — shifting to the right (or staying the same), never moving back to the left.

Algorithm

We solve this using the “two-pointer technique (sliding window).”

1. Start with the shelter index \(j\) at \(0\) (the leftmost shelter).
2. Scan houses from left to right (in ascending order of \(X\)), comparing whether the current shelter \(P_j\) or the next shelter \(P_{j+1}\) is closer.
3. If \(|x-P_{j+1}| \le |x-P_j|\), then the next shelter is equally close or closer, so advance \(j \leftarrow j+1\).
4. Keep advancing \(j\) until it no longer gets closer (until the condition no longer holds). At that point, \(|x-P_j|\) is the minimum distance.
5. Move on to the next house (\(j\) is not reset — it carries over as-is).

The key insight is that as the house \(x\) moves to the right, the boundary where “\(P_{j+1}\) is closer” also moves to the right, so \(j\) is incremented at most \(M-1\) times in total. Therefore, the entire process finishes in linear time.

(The <= in the code handles the case where the house is exactly at the midpoint and both distances are equal, advancing the pointer to the right. The minimum distance itself is the same either way, but this naturally lets the pointer drift rightward.)

Complexity

• Time complexity: \(O(N+M)\) (\(j\) is incremented at most \(M-1\) times in total)
• Space complexity: \(O(1)\) (excluding output; input arrays are stored separately)

Implementation Notes

• Since the input size is large, reading all at once with sys.stdin.buffer.read() is faster.

• Be careful not to forget while j + 1 < M, or you will get an out-of-bounds access.

• We only need to compare abs(x - P[j]) and abs(x - P[j+1]), yielding an \(O(N+M)\) solution that is faster than binary search (\(O(N\log M)\)).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    X = data[2:2 + N]
    P = data[2 + N:2 + N + M]

    j = 0
    out = []
    for x in X:
        while j + 1 < M and abs(x - P[j + 1]) <= abs(x - P[j]):
            j += 1
        out.append(str(abs(x - P[j])))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.