Олимпиадный тренинг

Задача . E. Жадный Лифт

Задача

В m-этажном (m > 1) офисе международной корпорации CodeForces установили новейшую систему управления лифтом. Она работает следующим образом.

Все этажи офиса последовательно пронумерованы целыми числами от 1 до m. В момент времени t = 0 лифт находится на первом этаже, лифт пустой и никто не ждет лифта на других этажах. Далее, в моменты времени t_i (t_i > 0) к лифту подходят люди. Для простоты будем считать, что один человек пользуется лифтом только один раз в рассматриваемый промежуток времени. Для каждого человека известно 3 параметра: момент времени, в который человек подходит к лифту, этаж, на котором человек находится изначально, и этаж, на который он хочет попасть.

Передвижение лифта между этажами происходит следующим образом. В момент времени t (t ≥ 0, t — целое) лифт всегда находится на каком-то этаже. Лифт сначала выпускает всех людей, которые находятся в лифте и хотят попасть на текущий этаж. Затем он впускает всех людей, которые ждут лифта на текущем этаже. Если человек подходит к лифту ровно в момент времени t, то он успевает в него сесть. Можно считать, что все эти действия (посадка и высадка из лифта) совершаются мгновенно. После этого лифт решает, в каком направлении ему переместиться, и в момент времени (t + 1) лифт попадает на выбранный этаж.

Лифт выбирает направление движения по следующему алгоритму.

Если лифт пустой, и в текущий момент времени ни на одном этаже никто его не ждет, то лифт остается на текущем этаже.
Иначе, пусть лифт находится на этаже номер x (1 ≤ x ≤ m). Тогда лифт вычисляет «приоритеты» направлений p_up и p_down: p_up — это сумма количества людей, которые ждут лифт на этажах с номерами больше x, и количества людей в лифте, которые хотят попасть на этаж с номером больше x; p_down — это сумма количества людей, которые ждут лифт на этажах с номерами меньше x, и количества людей в лифте, которые хотят попасть на этаж с номером меньше x. Если p_up ≥ p_down, то лифт поднимается на один этаж выше текущего (то есть с этажа x на этаж x + 1), иначе лифт опускается на один этаж ниже текущего (то есть с этажа x на этаж x - 1).

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

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

В первой строке заданы два целых числа, разделенных пробелом: n, m (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁵) — количество людей и этажей в здании соответственно.

В следующих n строках содержатся по три целых числа, разделенных пробелами: t_i, s_i, f_i (1 ≤ t_i ≤ 10⁹, 1 ≤ s_i, f_i ≤ m, s_i ≠ f_i) — момент времени, когда i-тый человек начнет ждать лифта, номер этажа, на котором изначально находится i-тый человек, и номер этажа, на который он хочет попасть.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примечание

В первом примере лифт действовал следующим образом:

t = 1. Лифт находится на этаже номер 1. Лифт пуст. На этаже номер 2 ждет один человек. p_up = 1 + 0 = 1, p_down = 0 + 0 = 0, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 2.
t = 2. Лифт находится на этаже номер 2. В лифт заходит один человек, который хочет попасть на этаж номер 7. p_up = 0 + 1 = 1, p_down = 0 + 0 = 0, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 3.
t = 3. Лифт находится на этаже номер 3. В лифте находится один человек, который хочет попасть на этаж номер 7. На этажах с номерами 4 и 6 лифт ждут два человека. p_up = 2 + 1 = 3, p_down = 0 + 0 = 0, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 4.
t = 4. Лифт находится на этаже номер 4. В лифте находится один человек, который хочет попасть на этаж номер 7. В лифт заходит один человек, который хочет попасть на этаж номер 8. На этаже с номером 6 лифт ждет один человек. p_up = 1 + 2 = 3, p_down = 0 + 0 = 0, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 5.
t = 5. Лифт находится на этаже номер 5. В лифте находятся два человека, которые хотят попасть на этажи с номерами 7 и 8 соответственно. На этаже с номером 6 лифт ждет один человек. p_up = 1 + 2 = 3, p_down = 0 + 0 = 0, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 6.
t = 6. Лифт находится на этаже номер 6. В лифте находятся два человека, которые хотят попасть на этажи с номерами 7 и 8 соответственно. В лифт заходит один человек, который хочет попасть на этаж номер 5. p_up = 0 + 2 = 2, p_down = 0 + 1 = 1, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 7.
t = 7. Лифт находится на этаже номер 7. Из лифта выходит человек, который хотел попасть на этаж номер 7. В лифте находятся два человека, которые хотят попасть на этажи с номерами 8 и 5 соответственно. p_up = 0 + 1 = 1, p_down = 0 + 1 = 1, p_up ≥ p_down. Значит, лифт перемещается на этаж номер 8.
t = 8. Лифт находится на этаже номер 8. Из лифта выходит человек, который хотел попасть на этаж номер 8. В лифте находится один человек, который хочет попасть на этаж номер 5. p_up = 0 + 0 = 0, p_down = 0 + 1 = 1, p_up < p_down. Значит, лифт перемещается на этаж номер 7.
t = 9. Лифт находится на этаже номер 7. В лифте находится один человек, который хочет попасть на этаж номер 5. p_up = 0 + 0 = 0, p_down = 0 + 1 = 1, p_up < p_down. Значит, лифт перемещается на этаж номер 6.
t = 10. Лифт находится на этаже номер 6. В лифте находится один человек, который хочет попасть на этаж номер 5. p_up = 0 + 0 = 0, p_down = 0 + 1 = 1, p_up < p_down. Значит, лифт перемещается на этаж номер 5.
t = 11. Лифт находится на этаже номер 5. Из лифта выходит человек, который хотел попасть на этаж номер 5. Лифт пуст и никто его не ждет, а значит, лифт остается на этаже номер 5.

Примеры

№	Входные данные	Выходные данные
1	3 10 1 2 7 3 6 5 3 4 8	7 11 8
2	2 10 1 2 5 7 4 5	5 9

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

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

Загруженные файлы

Нет