Чемпионат КРОК 2016 - Квалификация |
---|
Закончено |
В этой задаче от вас требуется промоделировать поведение однопоточного сервера. Серверу поступят n запросов, для каждого из которых дан момент поступления ti и продолжительность обработки di. Известно, что все ti различны.
При поступлении нового запроса сервер может совершить одно из трёх действий:
Как только сервер заканчивает обрабатывать очередной запрос, он переходит к следующему из очереди, если она не пуста. Считайте, что если какой-то запрос пришёл в момент времени x, и в этот же момент времени сервер освободился и очередь не пуста, то сначала начнёт обрабатываться запрос из очереди, а затем произойдет появление нового запроса.
Для каждого запроса найдите момент окончания его обработки или выведите для него -1, если он будет отклонён.
В первой строке входных данных содержатся целые числа n и b (1 ≤ n, b ≤ 200 000) — количество запросов и максимальный размер очереди соответственно.
Далее в n строках заданы описания запросов в хронологическом порядке. Каждое описание запроса записано на отдельной строке и состоит из двух целых чисел ti и di (1 ≤ ti, di ≤ 109), где ti — момент поступления i-го запроса, а di — продолжительность его обработки. Значения ti строго возрастают, то есть ti - 1 < ti для всех i > 1.
Выведите последовательность n целых чисел e1, e2, ..., en, где ei — момент окончания обработки i-го запроса (нумерация в порядке поступления) или - 1, если i-й запрос будет проигнорирован.
5 1
2 9
4 8
10 9
15 2
19 1
11 19 -1 21 22
4 1
2 8
4 8
10 9
15 2
10 18 27 -1
Рассмотрим первый пример.
Название |
---|