1760 . Ch2. Section 5. 黑夜下的步行
TopCoder
Tags
Description
招降了蘿莉的妁艷，儘管喪失了一些魔力，卻也套得了至關重要的情報......
原來學生們被控制皆是因為學校的鐘聲催眠了他們...而一切的源頭就在控制室......
這時就在楓音的陪伴下，他們朝著控制室的方向移動，
走著走著，妁艷漸漸的感覺到剛剛失去的精力逐漸回來了...
看著控制室的入口就在正前方那棟大樓中，妁艷漸漸的感到不捨
他想要把握這次獨處的機會，
他想要好好的享受這個時光，
他想要好好的利用這個時刻......
看著就在前方的大樓，妁艷明知道不該再遲疑，應該立刻趕過去...救他的妹妹
但卻也想與楓音繼續在一起......
妁艷這時想到了一個折衷的方案！
看了一下前方的道路，發現有些地方因為燈而明亮，有些地方則十分的暗
他將這n個位置不一樣的地方分別定為區域A1~An，
然後每個區域有兩個數值，分別是他們距離妁艷的距離以及那個地方的暗度(暗度越大代表這是個比較優的位置)
現在妁艷希望可以前往一個暗度比現在還要暗的地方，
卻又希望可以快點接近控制室(即距離當前妁艷越遠的地方)
想請問一下他最遠可以到的地方暗度有多暗？
如果說前面已經沒有位置比當前還暗，請輸出-1。
Input Format
第1行有一個數字n，代表妁艷分析了有n個區域
(n <= 300000)
第2行至第n+1行分別為每行分別各有兩個數字，代表著第A1個區域至第An個區域與妁艷的距離以及暗度。
Output Format
請印出一行數字，
每個數字之間以空白間隔，分別代表從編號1到編號n的位置最遠且比當前位置還暗的地方的暗度。
Sample Input 1
3
1 2
2 3
3 4
1 2
2 3
3 4
Sample Output 1
4 4 -1
Sample Input 2
5
2 5
1 2
3 4
4 3
5 2
2 5
1 2
3 4
4 3
5 2
Sample Output 2
-1 3 -1 -1 -1
Hints
Problem Source
原TIOJ1760 / problem setter: jeremy89183
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |