TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

96.2% (254/264)

Submission's AC Ratio

73.2% (520/710)

Tags

Description

從莎朗大街的街頭走到街尾,依序會經過n棟大樓,其高度分別為h1,h2,,hn。每棟大樓的頂樓都是停機坪,對每個k{1,2,,n},第k為飛行員想要從第ik棟大樓駕駛直升機飛到第jk棟大樓,其中1ik<jkn。她的飛行方式如下:先從第ik棟大樓向上直升至被稱為xik,jk的高度,接著在高度不變的情況下,向街尾飛至第ik大樓上方,最後降落在第jk棟大樓的頂端。為了避免撞到大樓,xik,jk不應小於hik+1hik+1+1hik+2+1hjk中的任一個,為了省油,xik,jk應盡量小,因此我們希望xik,jk恰為hik+1hik+1+1hik+2+1hjk+1的最小值。

Input Format

  1. 輸入第一行為n,第二行為h1,h2,,hn,對於每個k{1,2,,n},第k+2行為ikjk
  2. 2n10000001h1,h2,,hn1000000
  3. 同一行的數值間以空白隔開。
子任務(測資) 額外限制 分數
1 (0~7) n10 10
2 (8~51) n1000000 90

Output Format

對每個k{1,2,,n},輸出的第k行為xik,jk

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 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 (VSS, 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