分数: 300 点
问题陈述
目前,有 N 高桥在会议室。 的 i-th (1\le i\le N) 高桥的身高为 H _ i 并将离开房间 L _ i 分钟后。 高桥一旦离开房间,就再也不会回来。
你被给予 Q 有疑问,请按顺序回答。 对于 i-th (1\le i\le Q) 查询,给你一个整数 T _ i,所以找到房间里的高桥的最大高度 T _ i+\dfrac12 分钟后。 在这个问题的约束下,保证房间里至少有一个高桥 T _ i+\dfrac12 分钟后。
约束
- 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 几分钟后,房间里的所有高桥都还在那里。 因此,第一个查询的答案是 31,最大值 \lbrace31,26,3,15\rbrace.
5+\dfrac12 几分钟后,房间里就只有第四个高桥了。 因此,第三个查询的答案是 15,最大值 \lbrace15\rbrace.
示例输入 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