Отрезки
Отрезки
Никакие две буквы не должны иметь общей точки. А также общего тире
Руководство для телеграфистов
Директор Института Геометрии Отрезков (ИГО) принял Ааза в своём кабинете. Судя по обстановке, институт не бедствовал. Проблема на этот раз была в другом.
Мы не стоим без работы. Каждый раз, после начала сезона в чемпионатах по программированию, мы решаем множество задач на пересечение двух отрезков по заказу организаторов соревнований. Но это всё-таки рутина, и сотрудники начинают терять интерес. Кое-где даже вместо работы занимаются самодеятельностью - устраивают концерты для баяна при свечах. Можете ли сформулировать для нас задачу, отличную от этой, но не очень далеко от неё ушедшую по формулировке.
Ну например... Дано n отрезков на прямой. Для каждого отрезка требуется вычислить количество отрезков, которые имеют с ним хотя бы одну общую точку.
Сотрудники ИГО с энтузиазмом взялись за задачу. Более того - они поручили Вам написать программу для её решения.
Giriş verilənləri
Содержит один или несколько тестов. В первой строке каждого теста записано количество отрезков n (1 ≤ n ≤ 10^5
). Следующие n строк описывают отрезки: i-я строка содержит пару целых чисел L[i]
и R[i]
- координаты начала и конца i-го отрезка (-10^9
≤ L[i]
≤ R[i]
≤ 10^9
). Общая сумма значений n во входных данных не превосходит 10^5
. Входные данные завершаются нулём. Количество тестов не превосходит 10^4
.
Çıxış verilənləri
Для каждого теста в одной строке выведите n чисел как показано в примере: i-ое число - количество отрезков, с которыми i-ый отрезок имеет хотя бы одну общую точку, не считая его самого. Следуйте формату вывода максимально точно.
Nümunə
3 1 2 2 3 3 4 4 1 6 2 3 4 5 7 8 0
Case 1: 1 2 1 Case 2: 2 1 1 0