ABC463C - Tallest at the Moment

考え方

時系列にそって何かが起こる話なので、イベントソートで考えたいところ。
しかし、高橋くんが入室なら扱いやすいが、退出すなわちデータの削除は大変。
そこで、時間軸を反転し、逆再生で解いていくことを考える。

まず、クエリを全て先読みし、時刻が遅い順に並べておく。
また、高橋くんも、退出時刻が遅い順に並べておく。

そして、クエリを遅い順に見ていく。
あるクエリを見たときには、その時刻より後に退出した高橋くんをすべて部屋の中に戻せばよい。

これなら高橋くんの（データ的な意味で）退出が発生しないので、最高身長を変数 $1$ つで持てば十分。
クエリを処理するごとに本来のクエリ番号のところに結果を書き込んでいけばよい。
計算量は、ソートがボトルネックで $O(N \log N + Q \log Q)$。

入力を受け取る。

n: 4
h: {31, 26, 3, 15}
l: {4, 5, 5, 9}
q: 4
t: {3, 4, 5, 6}

クエリを「時刻、番号」で降順に並べる。

query: {(6,3), (5,2), (4,1), (3,0)}

また、各高橋くんについて、「退出時刻、身長」で降順に並べる。

vec: {(9,15), (5,26), (5,3), (4,31)}

何人目の高橋くんを見ているかの変数 id を用意し、$0$ で初期化する。
今いる高橋くんの最高身長を表す変数 mx を用意し、十分小さい値で初期化する。

id: 0
mx: 0
result: {0, 0, 0, 0}

$0$ 番のクエリを処理する。
退出時刻が $6$ より大きい高橋くんを追加し、最高身長を更新する。
元の $3$ 番目のクエリの答えは $15$ である。

query[0]: (6,3)
id: 1
mx: 15
result: {0, 0, 0, 15}

$1$ 番のクエリを処理する。
退出時刻が $5$ より大きい高橋くんはいない。
元の $2$ 番目のクエリの答えは $15$ である。

query[1]: (5,2)
id: 1
mx: 15
result: {0, 0, 15, 15}

$2$ 番のクエリを処理する。
退出時刻が $4$ より大きい高橋くんを $2$ 人とも追加し、最高身長を更新する。
元の $1$ 番目のクエリの答えは $26$ である。

query[2]: (4,1)
id: 3
mx: 26
result: {0, 26, 15, 15}

$3$ 番のクエリを処理する。
退出時刻が $3$ より大きい高橋くんを追加し、最高身長を更新する。
元の $0$ 番目のクエリの答えは $31$ である。

query[3]: (3,0)
id: 4
mx: 31
result: {31, 26, 15, 15}

特になし。

特になし。