| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 4 | 3 | 1 | 100.000% |
Юному Энакину Скайуокеру магистр Йода поручил, на первый взгляд, простое задание. Ему необходимо было покрасить забор специальной краской. Задание состояло из $n$ подзадач. Каждая из подзадач заключалась в покраске некоторого участка забора краской заданного цвета. Каждый цвет обозначался целым числом. Краска, которая была дана Энакину, как и любая другая, после того, как высыхала, меняла свой цвет. Но это происходило немного необычным образом.
Будем говорить, что два участка забора пересекаются, если они имеют не нулевую площадь пересечения. Разобьем все участки забора, на которые была нанесена краска, не некоторые множества. Вначале каждый отрезок отнесем к отдельному множеству. Если существуют пересекающиеся участки, которые относятся к различным множествам $A$ и $B,ドル обьединим $A$ и $B$. Будем делать так до тех пор, пока такие участки не перестанут существовать.
Теперь для каждого множества можно определить его цвет как среднее арифметическое всех цветов входящих в него участков. Зная эту величину для каждого множества, мы легко можем определить, какого цвета будет некоторая точка забора после высыхания краски. Будем говорить, что точка принадлежит множеству, если есть хотя бы один участок в множестве, который содержит в себе эту точку. Если точка забора не принадлежит ни одному множеству, она будет иметь цвет 0ドル,ドル иначе она будет иметь цвет соответствующего множества. Заметим, что точка не может принадлежать сразу двум множествам.
Пока Энакин занимался покраской забора, ему стало интересно, что же случится, если он закончит покраску после нанесения первых $i$ участков. В частности, его заинтересовал такой вопрос <<Точку какого наибольшего цвета можно будет найти на заборе после того, как краска высохнет?>>.
Первая строка входного файла содержит одно целое число $n$ (1ドル \le n \le 10^5$) --- количество участков забора, которые необходимо покрасить. В следующих $n$ строках находится по три целых числа $l,ドル $r,ドル $c$ (0ドル \le l < r \le 10^9, 1 \le c \le 10^9$) --- левая и правая границы $i$-го участка (левая граница включается, правая нет), а также цвет, в который необходмо покрасить соответствующий участок.
В $n$ строках необходимо вывести по одному вещественному числу с не менее чем тремя знаками после запятой. Число в $i$-ой строке должно обозначать максимальный цвет точки на стене, который можно было бы найти, если бы Энакин закончил покраску забора после выполнения первых $i$ подзадач.
6 0 1 1 2 5 2 3 7 3 6 8 4 9 11 5 7 10 6
1.00000 2.00000 2.50000 3.00000 5.00000 4.00000