1410. 弱弱的战壕

时间限制 1000 ms   内存限制 128 MB

永恒和mx正在玩一个即时战略游戏,名字嘛~~~~~~恕本人记性不好,忘了-_-b。 mx在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,射程可以达到无限(“mx不赢定了?!?”永恒ftING...@_@)。 但是,战壕有一个弱点,就是只能攻击它的左下方,说白了就是横纵坐标都不大于它的点(mx:“我的战壕为什么这么菜”ToT)。这样,永恒就可以从别的地方进攻摧毁战壕,从而消灭mx的部队。 战壕都有一个保护范围,同它的攻击范围一样,它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样,永恒就必须找到mx的战壕中保护对象最多的点,从而优先消灭它。 现在,由于永恒没有时间来计算,所以拜托你来完成这个任务: 给出这n个战壕的坐标xi、yi,要你求出保护对象个数为0,1,2……n-1的战壕的个数。

输入数据

第一行,一个正整数n(1< =n< =15000)
接下来n行,每行两个数xi,yi,代表第i个点的坐标
(1< =xi,yi< =32000)
注意:可能包含多重战壕的情况(即有数个点在同一坐标)

输出数据

输出n行,分别代表保护对象为0,1,2……n-1的战壕的个数。

样例输入

复制
5
1 1
5 1
7 1
3 3
5 5
 \n
 · \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
1
2
1
1
0
 \n
 \n
 \n
 \n
 \n

提交

请先 登录

Source

URAL1028战役版

© 2024 FAQs Contact About