イベントソート （平面走査）と呼ばれる方法で解くことができます。イベントソートとは、起こる出来事を時刻の順に並べて、その順に処理するテクニックです。

まず、「高橋くんの離脱」と「身長の最大値クエリ」を合わせた列を時刻順にソートします。

また、「現在会議室にいる高橋くんの身長」の多重集合 \(S\) も保持します。 \(S\) は時刻 \(0\) では \(S=\{H_1,H_2,\cdots, H_N\}\) です。

そして、時刻の昇順に処理していきます。

• 時刻 \(L_i\) に到達したら \(H_i\) を \(S\) から削除します。
• 時刻 \(T_i +1/2\) に到達したら、クエリ番号 \(i\) の答えはそのときの \(S\) の最大値です。

C++ では最大値が取得できる多重集合 \(S\) は std::multiset で管理できます。

よって、この問題を時間計算量 \(O((N+Q) \log (N+Q))\) 、空間計算量 \(O(N+Q)\) で解くことができます。

また、今回の問題の場合、時刻 \(T_i + 1/2\) の代わりに、すべての時刻を \(2\) 倍にして、

• \(L_i \to 2L_i\)
• \(T_i+1/2 \to 2T_i+1\)

とするとすべての時刻が整数で表せて便利です。

実装例1 (C++, 307ms)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	// 入力高速化
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	// イベント (時刻, タイプ, 番号 i)
	// タイプ 0 なら, 番号 i の高橋くんが離脱
	// タイプ 1 なら, クエリ番号 i に答える.
	vector<tuple<ll,int,int>> event;
	multiset<ll> st; // 高橋くんの身長の多重集合

	int n; cin >> n;
	vector<ll> h(n), l(n);

	for (int i=0; i<n; i++) {
		cin >> h[i] >> l[i];
		st.insert(h[i]);
		event.emplace_back(l[i] * 2, 0, i);
	}

	int q; cin >> q;
	vector<ll> t(q);
	
	for (int i=0; i<q; i++) {
		cin >> t[i];
		event.emplace_back(t[i] * 2 + 1, 1, i); 
	}

	sort(event.begin(), event.end());

	vector<ll> ans(q);
	for (auto [tim, typ, i]: event) {
		if (typ == 0) {
			st.erase(st.find(h[i])); // 多重集合から h[i] を 1 個だけ削除
		} else {
			ans[i] = *st.rbegin(); // 末尾の値を ans[i] に格納
		}
	}

	for (int i=0; i<q; i++) {
		cout << ans[i] << '\n';
	}

}

実装例2 (pypy3, 1562ms)

想定解でないイベントソートは特に Python だと TLE ギリギリ、もしくは TLE しがちだと感じます。

イベントの中身を tuple ではなく（64 bit の範囲に収まる） 1 つの整数にすると定数倍高速化できます。

定数倍高速化版 PyPy3 で 1016 ms

定数倍高速化していない↓

from sortedcontainers import SortedList

# イベント (時刻, タイプ, 番号 i)
# タイプ 0 なら, 番号 i の高橋くんが離脱
# タイプ 1 なら, クエリ番号 i に答える.
event = []
st = SortedList() # 高橋くんの身長の多重集合

n = int(input())
h = [0] * n
l = [0] * n

for i in range(n):
	h[i], l[i] = map(int,input().split())
	st.add(h[i])
	event.append((l[i] * 2, 0, i))

q = int(input())
t = list(map(int,input().split()))

for i in range(q):
	event.append((t[i] * 2 + 1, 1, i))

event.sort()

ans = [0] * q
for tim, typ, i in event:
	if typ == 0:
		# 多重集合から h[i] を 1 個だけ削除
		st.discard(h[i])
	else:
		# 末尾の値を ans[i] に格納
		ans[i] = st[-1]

print(*ans, sep='\n')