/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
現在、会議室に N 人の高橋くんがいます。 i 番目 (1\le i\le N) の高橋くんの身長は H _ i であり、今から L _ i 分後に会議室を去ります。 一度会議室を去った高橋くんはそれ以降会議室に戻ることはありません。
Q 個のクエリが与えられるので、順に答えてください。 i 番目 (1\le i\le Q) のクエリでは整数 T _ i が与えられるので、今から T _ i+\dfrac12 分後に会議室にいる高橋くんの身長の最大値を答えてください。 この問題の制約のもとで、今から T _ i+\dfrac12 分後には会議室に 1 人以上の高橋くんがいることが保証されます。
制約
- 1\le N\le3\times10 ^ 5
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9
- 1\le Q\le3\times10 ^ 5
- 0\le T _ i\lt L _ N\ (1\le i\le Q)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H _ 1 L _ 1 H _ 2 L _ 2 \vdots H _ N L _ N Q T _ 1 T _ 2 \ldots T _ Q
出力
Q 行にわたって出力せよ。 i 行目 (1\le i\le Q) には、i 番目のクエリに対する答えを出力せよ。
入力例 1
4 31 4 26 5 3 5 15 9 4 3 4 5 6
出力例 1
31 26 15 15
今から 3+\dfrac12 分後には、現在会議室にいる高橋くんは全員会議室にとどまっています。 よって、1 番目のクエリの答えは \lbrace31,26,3,15\rbrace の最大値である 31 です。
今から 5+\dfrac12 分後には、会議室には 4 番目の高橋くんだけがいます。 よって、3 番目のクエリの答えは \lbrace15\rbrace の最大値である 15 です。
入力例 2
10 587 138 772 155 755 404 519 408 529 432 169 586 114 632 249 656 329 972 299 984 14 443 801 824 276 399 314 300 510 311 580 498 930 359 5
出力例 2
329 329 329 755 755 755 755 329 755 329 329 329 755 772
Score : 300 points
Problem Statement
Currently, there are N Takahashi in a conference room. The i-th (1\le i\le N) Takahashi has a height of H _ i and will leave the room L _ i minutes from now. Once a Takahashi leaves the room, he never returns.
You are given Q queries, so answer them in order. For the i-th (1\le i\le Q) query, you are given an integer T _ i, so find the maximum height among the Takahashi who are in the room T _ i+\dfrac12 minutes from now. Under the constraints of this problem, it is guaranteed that at least one Takahashi will be in the room T _ i+\dfrac12 minutes from now.
Constraints
- 1\le N\le3\times10 ^ 5
- 1\le H _ i\le10 ^ 9\ (1\le i\le N)
- 1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9
- 1\le Q\le3\times10 ^ 5
- 0\le T _ i\lt L _ N\ (1\le i\le Q)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H _ 1 L _ 1 H _ 2 L _ 2 \vdots H _ N L _ N Q T _ 1 T _ 2 \ldots T _ Q
Output
Output Q lines. The i-th line (1\le i\le Q) should contain the answer to the i-th query.
Sample Input 1
4 31 4 26 5 3 5 15 9 4 3 4 5 6
Sample Output 1
31 26 15 15
3+\dfrac12 minutes from now, all Takahashi currently in the room are still there. Thus, the answer to the first query is 31, the maximum of \lbrace31,26,3,15\rbrace.
5+\dfrac12 minutes from now, only the fourth Takahashi is in the room. Thus, the answer to the third query is 15, the maximum of \lbrace15\rbrace.
Sample Input 2
10 587 138 772 155 755 404 519 408 529 432 169 586 114 632 249 656 329 972 299 984 14 443 801 824 276 399 314 300 510 311 580 498 930 359 5
Sample Output 2
329 329 329 755 755 755 755 329 755 329 329 329 755 772