2055 . 直升機（Helicopter）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb fhvirus
FHVirus
$\huge{WHP}$

User's AC Ratio

96.4% (162/168)

Submission's AC Ratio

68.4% (340/497)

Tags

TOI 2018-TOI-pre

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 1000000$且$1\leq h_1, h_2, \ldots, h_n \leq 1000000$。
  3. 同一行的數值間以空白隔開。
子任務（測資） 額外限制 分數
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

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

No. Testdata Range Score
1 0~7 10
2 8~51 90

Testdata and Limits

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