Skip to content

1143: 弱弱的战壕

题目

题目描述

火狐和夏茹正在玩一个即时战略游戏,名字嘛……恕本人记性不好,忘了qwq

火狐在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,射程可以达到无限。

但是,战壕有一个弱点,就是只能攻击它的左下方,说白了就是横纵坐标都不大于它的点。这样,夏茹就可以从别的地方进攻摧毁战壕,从而消灭火狐的部队。

战壕都有一个保护范围,同它的攻击范围一样,它可以保护处在它左下方的战壕。所有处于它保护范围的战壕都叫做它的保护对象。这样,夏茹就必须找到火狐的战壕中保护对象最多的点,从而优先消灭它。

现在,由于夏茹没有时间来计算,所以拜托你来完成这个任务:

给出这$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$的战壕的个数。

样例输入

text 5 1 1 5 1 7 1 3 3 5 5

样例输出

text 1 2 1 1 0

数据范围

题面已经给出

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!