Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Небоскреб

(Время: 1 сек. Память: 16 Мб Сложность: 77%)

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

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

Считается, что сегмент стоит устойчиво, если один из его блоков соприкасается с нижней стороной прямоугольника.

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

По данным о том, какие блоки сохранились, требуется определить положение верхнего блока в каждом вертикальном столбце.

Входные данные

Первая строка входного файла INPUT.TXT содержит одно целое число m (1 ≤ m ≤ 10 000). За ней следуют m строк, описывающих вертикальные столбцы. Описание производится в таком порядке: сначала записано число ai оставшихся целыми фрагментов этого вертикального столбца, за которым следуют 2ai чисел l(1)i, r(1)i, l(2)i, r(2)i, …, l(ai)i, r(ai)i, задающие нижние и верхние границы уцелевших фрагментов. При этом 1 ≤ l(1)i ≤ r(1)i , l(2)i ≤ r(2)i , . . . , l(ai)i ≤ r(ai)i ≤ 106, для всех допустимых i и j выполнено r(j)i < l(j+1)i - 1. Сумма всех ai не превосходит 100 000.

Выходные данные

В выходной файл OUTPUT.TXT выведите m чисел - высоты, на которых находится самый верхний блок в соответствующем вертикальном столбце.

Пример

INPUT.TXTOUTPUT.TXT
18
2 1 1 4 6
2 1 1 6 6
2 1 4 6 6
2 1 1 6 6
3 1 1 4 6 8 8
2 1 1 8 8
2 1 3 7 8
1 6 6
5 5 5 5 6 6 6 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483