eolymp
bolt
Try our new interface for solving problems
Məsələlər

Звезды

Звезды

Астрономы часто изучают звездные карты, где звезды представлены точками на плоскости, и каждая из них имеет свои декартовы координаты. Уровнем звезды назовем количество звезд, которое находится не выше и не правее от нее. Астрономы хотят знать распределение уровней звезд.

prb5619

Например, посмотрим на приведенную вверху карту. Уровень звезды номер 5 равен 3 (он формируется звездами с номерами 1, 2 и 4). Уровень звезд 2 и 4 равен 1. На этой карте только одна звезда имеет уровень 0, две звезды имеют уровень 1, одна звезда уровня 2, и одна звезда уровня 3.

Напишите программу, которая подсчитает количество звезд на каждом уровне заданной карты.

Входные данные

Первая строка содержит количество звезд n (1n15000). Следующие n строк описывают координаты звезд - два целых числа x и y в одной строке, 0x, y32000. В одной точке плоскости может находиться только одна звезда. Звезды перечислены в возрастающем порядке y координаты. Звезды с равной y координатой перечислены в порядке возрастания их x координаты.

Выходные данные

Вывести n строк, по одному числу в каждой из них. Первая строка должна содержать количество звезд уровня 0, вторая строка - количество звезд уровня 1 и так далее. Последняя строка содержит количество звезд уровня n - 1.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
5
1 1
5 1
7 1
3 3
5 5
Çıxış verilənləri #1
1
2
1
1
0
Müəllif Pavel Zaletsky
Mənbə 1999 III Ural Collegiate Programming Contest, Ekaterinburg, March 19 - 20, Problem А