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

Отрезки

Отрезки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Никакие две буквы не должны иметь общей точки. А также общего тире

Руководство для телеграфистов

Директор Института Геометрии Отрезков (ИГО) принял Ааза в своём кабинете. Судя по обстановке, институт не бедствовал. Проблема на этот раз была в другом.

Мы не стоим без работы. Каждый раз, после начала сезона в чемпионатах по программированию, мы решаем множество задач на пересечение двух отрезков по заказу организаторов соревнований. Но это всё-таки рутина, и сотрудники начинают терять интерес. Кое-где даже вместо работы занимаются самодеятельностью - устраивают концерты для баяна при свечах. Можете ли сформулировать для нас задачу, отличную от этой, но не очень далеко от неё ушедшую по формулировке.

Ну например... Дано n отрезков на прямой. Для каждого отрезка требуется вычислить количество отрезков, которые имеют с ним хотя бы одну общую точку.

Сотрудники ИГО с энтузиазмом взялись за задачу. Более того - они поручили Вам написать программу для её решения.

Giriş verilənləri

Содержит один или несколько тестов. В первой строке каждого теста записано количество отрезков n (1n10^5). Следующие n строк описывают отрезки: i-я строка содержит пару целых чисел L[i] и R[i] - координаты начала и конца i-го отрезка (-10^9L[i]R[i]10^9). Общая сумма значений n во входных данных не превосходит 10^5. Входные данные завершаются нулём. Количество тестов не превосходит 10^4.

Çıxış verilənləri

Для каждого теста в одной строке выведите n чисел как показано в примере: i-ое число - количество отрезков, с которыми i-ый отрезок имеет хотя бы одну общую точку, не считая его самого. Следуйте формату вывода максимально точно.

prb5156.gif

Nümunə

Giriş verilənləri #1
3
1 2
2 3
3 4
4
1 6
2 3
4 5
7 8
0
Çıxış verilənləri #1
Case 1: 1 2 1
Case 2: 2 1 1 0
Müəllif Ivan Kazmenko, Oleg Hristenko