この問題はいくつかの方法で解くことができますが、この解説では「最も身長の高い高橋くんになる可能性がある高橋くん」の情報のみを保持することで高速に解く方法について解説します。

\(2\) 人の高橋くんについて、一方の高橋くんがもう一方の高橋くんより背が高く、より遅くまで会議室にいる場合、後者の高橋くんははじめから会議室にいなくても答えが変わりません。

このような高橋くんをはじめに全員会議室から出しておくことで、\(H _ 1\ge H _ 2\ge\cdots\ge H _ N\) および \(L _ 1\le L _ 2\le\cdots\le L _ N\) を満たすようにできます。

すると、この問題は二分探索を使って解くことができます。

いなくても答えが変わらない高橋くんを会議室から出す部分については、stack を使って \(O(N)\) 時間で実現することができます。

全体の時間計算量は \(O(N+Q\log N)\) となります。

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

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;

    vector<pair<unsigned, unsigned>> takahashi;
    for (unsigned i = 0; i < N; ++i) {
        unsigned H, L;
        cin >> H >> L;
        while (!empty(takahashi) && takahashi.back().first <= H) // より早く退室するより背が低い高橋くんがいたら
            takahashi.pop_back(); // はじめに退室してもらう
        takahashi.emplace_back(H, L);
    }

    unsigned Q;
    cin >> Q;

    for (unsigned i = 0; i < Q; ++i) {
        unsigned T;
        cin >> T;
        // pair の第二要素で二分探索し、T 分より後に退出する中で最も背が高い高橋くんを見つける
        cout << ranges::upper_bound(takahashi, T, {}, &pair<unsigned, unsigned>::second)->first << endl;
    }
    return 0;
}