2055 . 直升機（Helicopter）
TopCoder
Tags
Description
從莎朗大街的街頭走到街尾，依序會經過$n$棟大樓，其高度分別為$h_1, h_2, \ldots, h_n$。每棟大樓的頂樓都是停機坪，對每個$k \in \{ 1, 2, \ldots, n \} $，第$k$為飛行員想要從第$i_k$棟大樓駕駛直升機飛到第$j_k$棟大樓，其中$1 \leq i_k < j_k \leq n$。她的飛行方式如下：先從第$i_k$棟大樓向上直升至被稱為$x_{i_k, j_k}$的高度，接著在高度不變的情況下，向街尾飛至第$i_k$大樓上方，最後降落在第$j_k$棟大樓的頂端。為了避免撞到大樓，$x_{i_k, j_k}$不應小於$h_{i_k} + 1$、$h_{i_k + 1} + 1$、$h_{i_k + 2} + 1$、$\ldots$、$h_{j_k}$中的任一個，為了省油，$x_{i_k, j_k}$應盡量小，因此我們希望$x_{i_k, j_k}$恰為$h_{i_k} + 1$、$h_{i_k + 1} + 1$、$h_{i_k + 2} + 1$、$\ldots$、$h_{j_k} + 1$的最小值。
Input Format
- 輸入第一行為$n$，第二行為$h_1, h_2, \ldots, h_n$，對於每個$k \in \{ 1, 2, \ldots, n \} $，第$k + 2$行為$i_k$與$j_k$。
- $2\leq n \leq 1000000$且$1\leq h_1, h_2, \ldots, h_n \leq 1000000$。
- 同一行的數值間以空白隔開。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~7) | $n\leq 10$ | 10 |
| 2 (8~51) | $n\leq 1000000$ | 90 |
Output Format
對每個$k \in \{ 1, 2, \ldots, n \} $，輸出的第$k$行為$x_{i_k, j_k}$。
Sample Input 1
8
3 2 5 7 3 1 4 5
2 5
1 4
3 8
6 7
3 6
4 5
2 7
3 5
3 2 5 7 3 1 4 5
2 5
1 4
3 8
6 7
3 6
4 5
2 7
3 5
Sample Output 1
3
3
2
2
2
4
2
4
3
2
2
2
4
2
4
Hints
Problem Source
2018 TOI入營考pE
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~7 | 10 |
| 2 | 8~51 | 90 |