從莎朗大街的街頭走到街尾,依序會經過$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$的最小值。
子任務(測資) | 額外限制 | 分數 |
1 (0~7) | $n\leq 10$ | 10 |
2 (8~51) | $n\leq 1000000$ | 90 |
對每個$k \in \{ 1, 2, \ldots, n \} $,輸出的第$k$行為$x_{i_k, j_k}$。
2018 TOI入營考pE
No. | Testdata Range | Score |
---|---|---|
1 | 0~7 | 10 |
2 | 8~51 | 90 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 |