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

Рассмотрим множество отрезков на прямой с целыми концами. Изначально множество пустое, в него могут добавляться отрезки, из него могут удалятся отрезки. После каждой операции вставки или удаления отрезка необходимо вывести общую длину объединения всех отрезков, лежащих на данный момент в множестве.

Giriş verilənləri

В первой строке входа записано целое число 1n100 000 - общее количество проделанных операций. Далее идут n строк, каждая из них устроена следующим образом. Первый символ - "+", если это операция вставки отрезка и "-", если это операция удаления отрезка. Далее в строке записаны через пробел два целых числа - левый и правый концы отрезка. Координаты концов по модулю не превосходят 1 000 000 000. Гарантируется, что удаляться будут только отрезки, которые перед этим были добавлены в множество. Одинаковые отрезки можно добавлять в множество. Каждый из них считается отдельным отрезком.

Çıxış verilənləri

В выход необходимо вывести ровно n чисел, по одному в строке - общую длину объединения всех отрезков в множестве после каждой из n операций добавления или удаления.

Nümunə

Giriş verilənləri #1
4
+ 1 3
+ 2 6
+ 5 7
- 2 6
Çıxış verilənləri #1
2
5
6
4
Müəllif М.Левин
Mənbə Зимние сборы в Харькове 2010 День 3