この問題は、いわゆる Successor/Predecessor を高速に求めることができれば、連想配列などを使って解くことができます。

より具体的には、与えられた \(X\) に対して

• \(X\le V _ i\) を満たす最小の \(V _ i\)
• \(X\ge V _ i\) を満たす最大の \(V _ i\)
• これらの \(V _ i\) に対する \((i,S _ i)\) の一覧もしくはそのうち \(i\) が最小のもの

を高速に求められればよいです。 これは、\(V _ i\) をソート済み列や平衡二分探索木など、\(V\) と対応する \((i,S _ i)\) の列を連想配列などで管理することで求めることができます。 連想配列を平衡二分探索木で実現している場合、これらをまとめることもできます。

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

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

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

    // V[i] と対応する (i, S[i]) の列
    map<int, vector<pair<int, string>>> merchandise;
    for (int i = 0; i < N; ++i) {
        string S;
        int V;
        cin >> S >> V;
        merchandise[V].emplace_back(make_pair(i, S));
    }

    for (int i = 0; i < Q; ++i) {
        int X;
        cin >> X;
        // X = V[i] となる V[i] が存在すれば
        if (merchandise.contains(X)) {
            // S をすべて出力
            for (string S : merchandise[X] | views::values) {
                cout << S << " ";
            }
            cout << endl;
        } else { // 存在しなければ
            // X 以上のうち最小の V[i] を求めて
            auto it = merchandise.lower_bound(X);
            // 大小関係をもとに場合分け
            if (it == merchandise.begin() || (it != merchandise.end() && prev(it)->first + it->first < 2 * X)) {
                cout << it->second[0].second << endl;
            } else if (it == merchandise.end() || it->first + prev(it)->first > 2 * X) {
                cout << prev(it)->second[0].second << endl;
            } else { // 距離が等しければ番号が小さいほう
                cout << min(it->second[0], prev(it)->second[0]).second << endl;
            }
        }
    }
    return 0;
}

from bisect import bisect_left


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

# V[i] と対応する (i, S[i]) の列
merchandise = dict()
for i in range(N):
    S, _V = input().split()
    V = int(_V)
    if not V in merchandise:
        merchandise[V] = []
    merchandise[V].append((i, S))

# V[i] を昇順に並べた列
prices = sorted(merchandise.keys())

for i in range(Q):
    X = input()
    # X = V[i] となる V[i] が存在すれば
    if X in merchandise:
        # S をすべて出力
        print(' '.join(S for i, S in merchandise[V]))
    else: # 存在しなければ
        # X 以上のうち最小の V[i] を求めて
        idx = bisect_left(prices, X)
        # 大小関係をもとに場合分け
        if idx == 0 or (idx < len(prices) and prices[idx - 1] + prices[idx] < 2 * X):
            print(merchandise[prices[idx]][0][1])
        elif idx == len(prices) or prices[idx - 1] + prices[idx] > 2 * X:
            print(merchandise[prices[idx - 1]][0][1])
        else: # 距離が等しければ番号が小さいほう
            print(min(merchandise[prices[idx]][0], merchandise[prices[idx - 1]][0])[1])