把整个过程看成“妖伞的位置不断向右推进”,并维护当前已经加入队伍但还没离开的人。
在一条数轴上有n(1<n<1000)个人,第i个人的出生点为 pi,终点为 qi(1≤pi<qi<109)。所有人的出生点两两不同,且按从小到大的顺序输入(p1<p2<⋅⋅⋅<pn);对于任意i,都有 pi<qi,即所有人都只会沿数轴正方向移动。
最开始,第1个人持有妖伞,并从自己的出生点p1出发前往终点q1。
移动过程中,所有已加入的人会形成一个队伍,并按照以下规则行动:
加入队伍:当当前持伞队伍经过某个人的出生点pi时,如果此人尚未加入过队伍,则该人立即加入到队伍末尾("经过"包括恰好停在该点的情况)。
离开队伍:当某个人到达自己的终点qi时,该人会立刻离开队伍,并且之后不会再次加入队伍。
妖伞交接:如果离开队伍的人恰好是当前持有妖伞的人,若此时队伍非空,则妖伞交给新的队首;若此时队伍为空,则妖伞会停留在当前位置不动,此后所有尚未加入过队伍的人中,出生点距离妖伞当前位置最近的人会先前往该位置取得妖伞,再继续前往自己的终点。若该人在前往取伞途中经过了其他尚未加入过队伍的人的出生点,这些人同样会按规则加入队伍末尾。
最近人的唯一性:题目保证所有人的出生点互不相同且严格递增,因此当队伍为空时,距离妖伞最近且尚未加入的人是唯一确定的。
定义第i 个人的贡献值为该人持有妖伞期间,妖伞实际发生位移的总距离。请输出每个人的贡献值。
第一行输入一个整数 n(1<n<1000),表示人数。 接下来 n 行,每行输入两个整数 pi,qi(1<pi<qi<109),表示第 i个人的出生点和终点,满足p1<p2<...<pn。
输出一行几个整数,第i个整数表示第i个人持有妖伞期间,妖伞实际发生位移的总距离。
输入
4
1 10
5 6
9 30
20 25
输出
9 0 20 0
说明
初始时,第1个人在位置1持有妖伞并出发。当队伍移动到位置5时,第2个人加入;当队伍移动到位置9时,第3个人加入;第1个人到达终点10后离开,贡献为10−1=9。
随后第2个人成为新的队首,但其终点6已在当前位置左侧,立刻离队,贡献为0。队伍继续前进,第4个人在位置 20 加入;第4个人到达
终点 25时离队,在此之前未成为持伞者,贡献为0。最终第3个人持有妖伞从位置10移动到终点30,贡献为 30−10=20