Лифт
(Время: 3 сек. Память: 64 Мб Сложность: 62%)
В современном многоэтажном офисе крупной компании установлен новый лифт. В компании работает n сотрудников. Для проверки эффективности системы управления лифтом требуется провести моделирование его работы в конце рабочего дня, когда все сотрудники должны покинуть здание и спуститься на первый этаж.
В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван, либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если несколько вызовов поступает одновременно, активным становится вызов от сотрудника с меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все люди выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия (лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается решение, на какой вызов лифт должен отреагировать).
Требуется написать программу, которая по описанию вызовов лифта для каждого сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m – количество людей, вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).
Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых числа ti и ai – секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)
Выходные данные
В выходной файл OUTPUT.TXT выведите n целых чисел: для каждого сотрудника требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 4 2 3 2 4 5 2 5 3 9 3 |
6 12 6 12 12
|
Пояснение к примеру
Пример работы лифта по шагам:
Время |
1 этаж |
2 этаж |
3 этаж |
4 этаж |
0 |
[] |
|
|
|
1 |
[] |
|
|
|
2 |
[]↑3 |
|
☺1 |
☺2 |
3 |
|
[]↑3 |
☺1 |
☺2 |
4 |
|
|
[]←☺1 |
☺2 |
5 |
|
[☺1] ←☺3 |
☺4 |
☺2 |
6 |
[☺1→, ☺3→]↑4 |
|
☺4 |
☺2 |
7 |
|
[]↑4 |
☺4 |
☺2 |
8 |
|
|
[]↑4 ☺4 |
☺2 |
9 |
|
|
☺4☺5 |
[]←☺2 |
10 |
|
|
[☺2]←☺4☺5 |
|
11 |
|
[☺2, ☺4, ☺5] |
|
|
12 |
[☺2→, ☺4→, ☺5→] |
|
|
|
Используемые обозначения:
|
Пояснение |
[] |
обозначение лифта |
[]↑j |
лифт движется на активный вызов, сделанный на j-м этаже |
☺i |
i-й сотрудник ждет лифта |
←☺i |
i-й сотрудник заходит в лифт |
[☺i] |
i-й сотрудник находится в лифте |
[☺i→] |
i-й сотрудник выходит из лифта |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|