この問題は、平衡二分探索木などを適切に使うことで解くことができます。 より具体的には、平衡二分探索木などでまだ出動していない消防車を管理し、次のようなクエリに答えられるようにすればよいです。

• 座標 \(x\) が与えられる。残っている消防車で座標 \(x\) 以上にいるもののうち、座標が最も小さいものを求めよ。
• 座標 \(x\) が与えられる。残っている消防車で座標 \(x\) 以下にいるもののうち、座標が最も大きいものを求めよ。

これらのクエリの結果を比較することで答えを求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    // 座標から性能と番号を返す連想配列
    map<int, pair<int, int>> ambulance;
    for (int i = 0; i < N; ++i) {
        int X, S;
        cin >> X >> S;
        ambulance[X] = make_pair(S, i + 1);
    }

    for (int i = 0; i < Q; ++i) {
        int P;
        cin >> P;

        // P 以上でもっとも座標が小さい消防車を求める
        auto it = ambulance.lower_bound(P);
        auto ans = it;
        // P 未満のものが出動するかを判定し
        if (it == ambulance.end() || (it != ambulance.begin() && make_tuple(abs(it->first - P), -it->second.first, it->second.second) > make_tuple(abs(prev(it)->first - P), -prev(it)->second.first, prev(it)->second.second))) {
            ans = prev(it);
        }
        // 番号を出力
        cout << ans->second.second << endl;

        // 出動したら連想配列から消す
        ambulance.erase(ans);
    }
    return 0;
}

from sortedcontainers import SortedSet


N, Q = map(int, input().split())

# 座標と性能と番号の組を管理する
ambulance = SortedSet()
for i in range(N):
    X, S = map(int, input().split())
    ambulance.add((X, S, i + 1))

for i in range(Q):
    P = int(input())

    # P 以上でもっとも座標が小さい消防車を求める
    over = ambulance.bisect_left((P, 0, 0))
    ans = over
    # P 未満のほうが出動するかを判定し
    if over == len(ambulance) or (over != 0 and (abs(ambulance[over][0] - P), -ambulance[over][1], ambulance[over][2]) > (abs(ambulance[over - 1][0] - P), -ambulance[over - 1][1], ambulance[over - 1][2])):
        ans -= 1
    # 番号を出力
    print(ambulance[ans][2])

    # 出動したらリストから消す
    ambulance.pop(ans)