Overview

Fire stations are lined up on a straight line. For each fire location \(P_j\), we select “the closest undeployed fire truck (if equidistant, the one with higher performance; if still tied, the one with the smaller index)” and make that fire truck unavailable for future use. This process is repeated \(Q\) times.

Analysis

Key Observation

The fire station coordinates are sorted in ascending order: \(X_1 < X_2 < \cdots < X_N\). For a given point \(P\), the closest fire station is usually either “the station immediately to the left of \(P\)” or “the station immediately to the right of \(P\).”

The tricky part is that deployed fire trucks (stations) disappear along the way. However, even so, it suffices to consider only two candidates:

• “Among undeployed stations to the left of \(P\), the rightmost one (= left nearest neighbor)”
• “Among undeployed stations at or to the right of \(P\), the leftmost one (= right nearest neighbor)”

This is because any station farther to the left necessarily has a greater distance, and the same applies to the right side.

Therefore, for each query we: 1. Find the insertion position of \(P\) (where it would go in \(X\)) using binary search 2. Quickly retrieve the “undeployed right neighbor” and “undeployed left neighbor” from that position 3. Compare the 2 candidates by: distance → performance → index 4. Remove the selected station from the “undeployed set”

and repeat.

Why the Naive Approach Fails

If we scan all undeployed stations for each fire to find the optimal one, the worst case is \(O(NQ)\). Since the constraint is \(N \le 2 \times 10^5\), this will definitely not be fast enough.

What we need is a data structure that can retrieve the predecessor/successor in \(O(\log N)\) from the “set of undeployed stations.”

Algorithm

Data Structure Used: Fenwick Tree (BIT)

We maintain a Fenwick Tree (BIT) as an array of length \(N\), where:

• \(1\) if undeployed
• \(0\) if deployed

What BIT can do: - Prefix sum (cumulative total from the beginning) in \(O(\log N)\) - “The smallest position where the prefix sum reaches \(k\)” (position of the \(k\)-th 1) in \(O(\log N)\)

Using this, we can achieve the following:

Successor (nearest undeployed to the right)

We want to find “the first position with a 1 at or after position \(i\).”

• Let \(before = sum(i-1)\) be the number of 1s up to \(i-1\)
• Let \(total = sum(N)\) be the total number of 1s
• If \(before == total\), there is no undeployed station to the right
• Otherwise, the position of the \((before+1)\)-th 1 is the successor

Predecessor (nearest undeployed to the left)

We want to find “the last position with a 1 at or before position \(i\).”

• Let \(cnt = sum(i)\) be the number of 1s up to \(i\)
• If \(cnt == 0\), there is no undeployed station to the left
• Otherwise, the position of the \(cnt\)-th 1 is the predecessor

Query Processing Flow

For each fire location \(P\):

1. Use bisect_left(X, P) to find the leftmost insertion position pos (0-based). This means “the smallest pos such that \(X_{pos} \ge P\)” (or \(N\) if none exists).
2. Convert to 1-indexed: k = pos + 1 (to align with station numbers)
3. Right candidate: right = successor(k) (nearest neighbor on the \(X \ge P\) side)
4. Left candidate: left = predecessor(k-1) (nearest neighbor on the \(X < P\) side)
5. Compare the candidates (at most 2) using the following key and select the minimum:
   • Distance: \(|X_i - P|\)
   • Performance: higher is preferred → use \(-S_i\) for comparison
   • Index: smaller is preferred → \(i\)

In other words, the comparison key is (distance, -performance, index). 6. Output the selected station best, and perform add(best, -1) on the BIT to remove it from the undeployed set.

Complexity

• Time complexity: Initialization \(O(N)\) (building the BIT with all 1s) Each query: binary search \(O(\log N)\) + predecessor/successor \(O(\log N)\) + deletion \(O(\log N)\) Total: \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The property that “the nearest neighbor candidates are only the left and right two” is the core insight. We avoid searching for the minimum distance across all stations.

• Since BIT is 1-indexed, we convert the bisect_left result (0-indexed) to k = pos + 1.

• To handle the tie-breaking priority when distances are equal (higher performance first, then smaller index), we set the comparison key to (distance, -S[i], i).

• Removing a deployed station is done simply by adding -1 to the BIT — there is no need to directly manipulate a set.

  Source Code

import sys
from bisect import bisect_left

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n: int):
        self.n = n
        bit = [0] * (n + 1)
        # build with all 1s in O(n)
        for i in range(1, n + 1):
            bit[i] += 1
            j = i + (i & -i)
            if j <= n:
                bit[j] += bit[i]
        self.bit = bit

    def add(self, i: int, v: int) -> None:
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += v
            i += i & -i

    def sum(self, i: int) -> int:
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def kth(self, k: int) -> int:
        # 1-indexed: smallest idx with prefix sum >= k (k in [1..total])
        idx = 0
        bit = self.bit
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= self.n and bit[nxt] < k:
                idx = nxt
                k -= bit[nxt]
            step >>= 1
        return idx + 1

    def successor(self, i: int):
        if i < 1:
            i = 1
        if i > self.n:
            return None
        total = self.sum(self.n)
        before = self.sum(i - 1)
        if before == total:
            return None
        return self.kth(before + 1)

    def predecessor(self, i: int):
        if i < 1:
            return None
        if i > self.n:
            i = self.n
        cnt = self.sum(i)
        if cnt == 0:
            return None
        return self.kth(cnt)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    X = [0] * (N + 1)
    S = [0] * (N + 1)
    X0 = [0] * N  # 0-based for bisect

    for i in range(1, N + 1):
        xi = next(it)
        si = next(it)
        X[i] = xi
        S[i] = si
        X0[i - 1] = xi

    fw = Fenwick(N)

    out_lines = []
    for _ in range(Q):
        p = next(it)
        pos = bisect_left(X0, p)  # 0..N
        k = pos + 1               # 1..N+1

        right = fw.successor(k)
        left = fw.predecessor(k - 1)

        best = None
        best_key = None

        if left is not None:
            best = left
            best_key = (p - X[left] if p >= X[left] else X[left] - p, -S[left], left)
        if right is not None:
            key = (X[right] - p if X[right] >= p else p - X[right], -S[right], right)
            if best is None or key < best_key:
                best = right
                best_key = key

        out_lines.append(str(best))
        fw.add(best, -1)

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.