TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

98.2% (54/55)

Submission's AC Ratio

69.4% (136/196)

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

  1. 輸入第一行為$n$,第二行為$h_1, h_2, \ldots, h_n$,對於每個$k \in \{ 1, 2, \ldots, n \} $,第$k + 2$行為$i_k$與$j_k$。
  2. $2\leq n \leq 100000$且$1\leq h_1, h_2, \ldots, h_n \leq 1000000$。
  3. 同一行的數值間以空白隔開。
子任務(測資) 額外限制 分數
1 (0~7) $n\leq 10$ 10
2 (8~51) $n\leq 100000$ 90

Output Format

對每個$k \in \{ 1, 2, \ldots, n \} $,輸出的第$k$行為$x_{i_k, j_k}$。

Sample Input

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

Sample Output

Sample Output #1
3
3
2
2
2
4
2
4

Hints

Problem Source

2018 TOI入營考pE

Subtasks

For Testdata: 0 ~ 7, Score: 10
For Testdata: 8 ~ 51, Score: 90
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 262144 262144
23 1000 262144 262144
24 1000 262144 262144
25 1000 262144 262144
26 1000 262144 262144
27 1000 262144 262144
28 1000 262144 262144
29 1000 262144 262144
30 1000 262144 262144
31 1000 262144 262144
32 1000 262144 262144
33 1000 262144 262144
34 1000 262144 262144
35 1000 262144 262144
36 1000 262144 262144
37 1000 262144 262144
38 1000 262144 262144
39 1000 262144 262144
40 1000 262144 262144
41 1000 262144 262144
42 1000 262144 262144
43 1000 262144 262144
44 1000 262144 262144
45 1000 262144 262144
46 1000 262144 262144
47 1000 262144 262144
48 1000 262144 262144
49 1000 262144 262144
50 1000 262144 262144
51 1000 262144 262144