Задача

10 /10


Отрезки

Задача

Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
 
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
 
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

 
Примеры
Входные данные Выходные данные
1
3
1 3
4 5
2 4
1 2 1
2
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
1 2 3 4 5 4 3 2 1

 
 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6416
Комментарий учителя