Overview

This problem involves sequentially selecting the closest “not yet dispatched” fire truck to each fire location from \(N\) fire stations. You need to efficiently find candidates while considering tiebreaking rules (performance value, station number) when distances are equal.

Analysis

1. Narrowing Down Candidate Fire Trucks

For a fire occurring at coordinate \(P_j\), the candidate fire trucks can be narrowed down to the following two: - Among currently standby fire stations to the left of coordinate \(P_j\) (\(X_i \leq P_j\)), the one closest to \(P_j\). - Among currently standby fire stations to the right of coordinate \(P_j\) (\(X_i \geq P_j\)), the one closest to \(P_j\).

These two candidates are compared, and one is selected according to the problem’s priority rules (distance \(\to\) performance value \(\to\) station number).

2. Limitations of a Naive Approach

If we scan all fire stations for each fire report to find the standby station with the shortest distance, it takes \(O(N)\) per query. The total becomes \(O(NQ)\), which does not meet the time limit under the constraints \(N, Q \leq 2 \times 10^5\).

3. Key Points for Optimization

We need to speed up the operation of “finding the nearest station to a specific index among standby fire stations.” Since fire stations are sorted by coordinate, we would like to use binary search, but the “standby” status changes every time a fire truck is dispatched, so a simple array cannot handle this.

Therefore, we use a Fenwick Tree (BIT: Binary Indexed Tree). - Each fire station is managed as 1 if standby, 0 if dispatched. - We use bisect to find the insertion position (index \(k\)) for \(P_j\). - Using prefix sums on the BIT, we can determine “how many standby fire trucks exist before index \(k\).” - Using binary lifting on the BIT, we can identify “the index of the \(m\)-th existing standby fire station” in \(O(\log N)\).

Algorithm

1. Initialization:
   • Read the coordinates \(X\) and performance values \(S\) of the fire stations.
   • Build the BIT and set all \(N\) stations to 1 (standby).
2. For each query \(P_j\):
   • Use bisect_left to find the smallest index \(k\) such that \(X_i \geq P_j\).
   • Using the BIT’s prefix sum, calculate count_before, the total number of standby fire trucks to the left of index \(k\).
   • Left candidate: Find the count_before-th standby fire station using binary lifting on the BIT.
   • Right candidate: Find the (count_before + 1)-th standby fire station using binary lifting on the BIT.
   • Select one from the two candidates according to the priority rules: distance, performance value, then station number.
   • Update the selected fire station’s BIT value to 0 (add -1) to mark it as dispatched.
3. Output:
   • Output the station numbers selected for each query in order.

Complexity

• Time Complexity: \(O(N + Q \log N)\)
  • BIT initialization takes \(O(N)\).
  • For each query, binary search (bisect), binary lifting on the BIT, and BIT update each take \(O(\log N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store fire station information and the BIT.

Implementation Notes

• Binary lifting on the BIT: Combining a regular binary search with BIT queries results in \(O(\log^2 N)\), but by leveraging the BIT’s structure through binary lifting, this can be reduced to \(O(\log N)\).

• Fast I/O: In Python, when dealing with large amounts of data, using sys.stdin.read().split() and sys.stdout.write can significantly reduce execution time.

• 1-indexed: Since BITs are typically implemented as 1-indexed, care must be taken when converting between the 0-indexed management of fire stations.

  Source Code

import sys
from bisect import bisect_left

def solve():
    # Fast I/O: Reading all input at once is efficient in Python
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: Number of fire stations, Q: Number of fire calls
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # Coordinates X and performance values S for each station
    # Stations are given in increasing order of X_i
    X = [int(input_data[i]) for i in range(2, 2 + 2 * N, 2)]
    S = [int(input_data[i]) for i in range(3, 2 + 2 * N, 2)]
    # Fire call coordinates P
    P = [int(input_data[i]) for i in range(2 + 2 * N, 2 + 2 * N + Q)]

    # Fenwick Tree (BIT) to track available stations
    # bit[i] stores the count of available stations in a range
    # Initializing BIT in O(N) where each station is initially available (1)
    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] = i & -i
    
    # Number of bits required for binary lifting on BIT
    blen = N.bit_length()
    
    results = []
    total_available = N
    
    for pj in P:
        # Find the index where the fire coordinate pj would be inserted in X
        # k is the smallest index such that X[k] >= pj
        k = bisect_left(X, pj)
        
        # Count available stations with index < k (stations to the left of pj)
        # This is equivalent to bit_query(k)
        count_before = 0
        temp_k = k
        while temp_k > 0:
            count_before += bit[temp_k]
            temp_k -= temp_k & -temp_k
        
        i_L = -1 # Nearest available station to the left
        i_R = -1 # Nearest available station to the right
        
        # Use binary lifting on the BIT to find the k-th available station's index
        # 1. Find the closest available station with index < k (the count_before-th available)
        if count_before > 0:
            idx = 0
            temp_count = count_before
            for i in range(blen - 1, -1, -1):
                next_idx = idx + (1 << i)
                if next_idx <= N:
                    val = bit[next_idx]
                    if val < temp_count:
                        idx = next_idx
                        temp_count -= val
            i_L = idx
            
        # 2. Find the closest available station with index >= k (the (count_before + 1)-th available)
        if count_before < total_available:
            idx = 0
            temp_count = count_before + 1
            for i in range(blen - 1, -1, -1):
                next_idx = idx + (1 << i)
                if next_idx <= N:
                    val = bit[next_idx]
                    if val < temp_count:
                        idx = next_idx
                        temp_count -= val
            i_R = idx
            
        # Tie-breaking logic:
        # Distance (min) > Performance (max) > Station Index (min)
        if i_L != -1 and i_R != -1:
            dL = pj - X[i_L]
            dR = X[i_R] - pj
            if dL < dR:
                chosen = i_L
            elif dR < dL:
                chosen = i_R
            else:
                # Distances are equal, compare performance values
                if S[i_L] > S[i_R]:
                    chosen = i_L
                elif S[i_R] > S[i_L]:
                    chosen = i_R
                else:
                    # Performances are equal, pick smaller index
                    chosen = i_L # i_L is always < i_R
        elif i_L != -1:
            chosen = i_L
        else:
            chosen = i_R
            
        # Store the 1-indexed station number
        results.append(chosen + 1)
        
        # Update BIT: Mark the chosen station as unavailable (set to 0)
        temp_idx = chosen + 1
        while temp_idx <= N:
            bit[temp_idx] -= 1
            temp_idx += temp_idx & -temp_idx
        total_available -= 1
        
    # Final output using fast join and sys.stdout
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.