F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 3755. -- Pty爬山

3755: Pty爬山

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 177  Solved: 32
[Submit][Status][Discuss]

Description

在Pty学校附近,有一座名之为岳之麓的高山。Pty很喜欢和(哔——)一起爬山。
山的平面模型如下:
山由一个顶点集:A1,A2…An给定,保证Ai的x单调递增。我们将Ai和Ai+1之间连上线段,表示山的某一段。如下图所示:
 
Pty想要爬到这座山的最高的顶点,当两个顶点的高度相同时,我们认为x比较大的顶点要高一些。Pty不是盲人,所以他将会在爬山时采取一些策略,使得他能够尽量快的到达最高的顶点。
Pty从初始的顶点出发,往左右看去,他将朝他能够看到的最高的顶点方向走去。当走到每一个顶点时,他都会重新观察,如果这时看到的顶点比之前看到的顶点还要高,那么他将选择此时看到的顶点走去,直到他到达最高点为止。
例如上图中:Pty从A4点出发。他能够看到的最高点是A6,所以他将会向右侧走去。当他到达A5号点时,能够看到A1点比A6点更高,所以他会调转方向,向左侧走去。由于A1是最高的顶点,所以他将一直往左侧走,直到到达A1为止。
Pty想知道从每一个顶点出发,分别需要走过多少段才能到达最高点。例如上图中从A4出发需要走过5段才能到达最高点。

Input

第一行输入n,表示n个顶点。
接下来n行,每行两个整数xi, yi,表示第i个顶点的坐标。
输入保证xi单调递增。

Output

输出共n行:第i行表示从第i个顶点出发走到最高点需要经过多少步。

Sample Input

5
1 5
2 4
3 9
4 0
5 2

Sample Output

2
1
0
1
2

HINT


100%的数据满足:n<=200000, xi<=10^6, yi<= 10^6


此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!

Source

[Submit][Status][Discuss]

HOME Back