시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 0 | 0 | 0 | 0.000% |
В современном многоэтажном офисе крупной компании установлен новый лифт. В компании работает n сотрудников. Для проверки эффективности системы управления лифтом требуется провести моделирование его работы в конце рабочего дня, когда все сотрудники должны покинуть здание и спуститься на первый этаж.
В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван, либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если несколько вызовов поступает одновременно, активным становится вызов от сотрудника с меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все люди выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия (лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается решение, на какой вызов лифт должен отреагировать).
Требуется написать программу, которая по описанию вызовов лифта для каждого сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.
Первая строка входных данных содержит целые числа n и m — количество людей, вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).
Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)
Выходные данные должны содержать n целых чисел, для каждого сотрудника требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
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-й сотрудник выходит из лифта |