Overview

Given \(N\) fire stations lined up on a straight line, for each of \(Q\) fire reports, we need to dispatch the closest available fire truck among those on standby. Since a dispatched fire truck can no longer be used afterward, we need to manage them dynamically.

Analysis

Key Observations

1. We need to find the “closest fire truck on standby” each time: For a fire location \(P_j\), we select the closest fire station among those that haven’t been dispatched yet. If distances are equal, we choose the one with the larger performance value \(S_i\), and if those are also equal, the one with the smaller index.

2. The coordinates \(X_i\) of fire stations are strictly increasing: All values are distinct. Because of this, for any fire location, there are at most 2 fire stations at the same distance (one on the left and one on the right).

3. One fire station is removed with each dispatch: We need a data structure that can efficiently search and delete elements while managing data dynamically.

Problem with the Naive Approach

Scanning all fire stations each time to find the closest one results in \(O(NQ)\), which amounts to roughly \(4 \times 10^{10}\) operations when \(N, Q\) are at most \(2 \times 10^5\), causing TLE.

Solution Strategy

Use a balanced binary search tree (sorted list) to manage the fire stations on standby in coordinate order. By performing binary search for fire location \(P_j\), we can find the closest candidate in \(O(\log N)\).

Algorithm

1. Data Structure Preparation: Store the fire stations on standby in a SortedList as tuples \((X_i, -S_i, i)\). We use \(-S_i\) because when distances are equal, we want to prioritize the larger performance value (since tuple comparison prioritizes the smaller value, we negate the sign).

2. Processing Each Fire Report:

   • For fire location \(P_j\), find the insertion position pos using bisect_left((P, -∞, -1)).
   • Check two candidates: pos - 1 (nearest candidate on the left) and pos (nearest candidate on the right).
   • Compute the comparison key \((|X_i - P_j|, -S_i, i)\) for each candidate and select the one with the smallest tuple.
     • Minimum distance → Maximum performance value (smallest \(-S_i\)) → Smallest index
   • Remove the selected fire station from the SortedList and output the result.

3. Why Two Candidates Suffice: Since all \(X_i\) are distinct, checking the left neighbor and right neighbor of the fire location in the sorted list covers all candidates with minimum distance. There can never be three or more fire stations at the same distance.

Concrete Example

With \(X = [2, 5, 8]\), \(S = [3, 1, 3]\) and fire location \(P = 5\): - pos is at the position of \((5, ...)\) → candidates are pos-1 (coordinate 2) and pos (coordinate 5) - Distances: coordinate 2 has \(|2-5|=3\), coordinate 5 has \(|5-5|=0\) - The fire station at coordinate 5 (fire station 2) is dispatched

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Initialization with \(N\) insertions (each \(O(\log N)\)), and for each query, binary search and deletion (each \(O(\log N)\))
• Space complexity: \(O(N)\)

Implementation Notes

• Tuple Design: By using \((X_i, -S_i, i)\), we can directly leverage Python’s tuple comparison for priority determination. Distance comparison is done separately with abs(X_i - P), and when distances are equal, the 2nd and 3rd elements of the tuple automatically handle tiebreaking.

• Search Key for bisect_left: By using (P, -∞, -1), if a fire station with coordinate exactly \(P\) exists, pos points to that position; otherwise, it points to the smallest coordinate greater than \(P\). This way, we only need to check the two positions pos-1 and pos.

• sortedcontainers.SortedList: This is not in Python’s standard library, so we use sortedcontainers. It is often available in Python environments for competitive programming.

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(input_data[idx]), int(input_data[idx+1])
    idx += 2
    
    X = [0] * N
    S = [0] * N
    for i in range(N):
        X[i] = int(input_data[idx])
        S[i] = int(input_data[idx+1])
        idx += 2
    
    # We need to efficiently find the closest available fire station to a given point.
    # On ties in distance, pick highest S, then smallest index.
    
    # We'll use a SortedList of (X[i], -S[i], i) for available stations.
    # For each query, we need to find candidates near P using binary search.
    
    available = SortedList()
    for i in range(N):
        available.add((X[i], -S[i], i))
    
    out = []
    
    for _ in range(Q):
        P = int(input_data[idx])
        idx += 1
        
        # Binary search for position of P in available
        # We want to check the element just before and at the insertion point
        pos = available.bisect_left((P, float('-inf'), -1))
        
        best = None
        best_key = None  # (distance, -S[i], i)
        
        # Check candidates around pos
        for p in (pos - 1, pos):
            if 0 <= p < len(available):
                xi, neg_si, i = available[p]
                dist = abs(xi - P)
                key = (dist, neg_si, i)
                if best_key is None or key < best_key:
                    best_key = key
                    best = (xi, neg_si, i)
        
        # The above checks at most 2 candidates. But there could be ties in distance
        # at positions further away. For example, if pos-1 and pos have the same distance,
        # we handled it. But what if pos+1 also has the same distance?
        # Actually, since X values are strictly increasing, at most 2 stations can be
        # equidistant (one on each side). But after removals, the sorted list entries
        # are a subset, so at most one on each side at closest distance.
        # Wait, X are strictly increasing, so all X[i] are distinct. In the sorted list,
        # keyed by (X[i], ...), X values are distinct. So bisect gives us at most
        # one candidate on each side at minimum distance. That's correct.
        
        out.append(str(best[2] + 1))
        available.remove(best)
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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