VK Cup 2012 Раунд 3 |
---|
Закончено |
У Поликарпа есть очень много работ. Каждая работа характеризуется тремя целыми числами li, ri и ti. Тройка (li, ri, ti) означает, что для выполнения работы i нужно выбрать целое число si (li ≤ si; si + ti - 1 ≤ ri), тогда работа будет выполняться непрерывно ti единиц времени, начиная с момента времени si и до момента времени si + ti - 1, включительно. Иными словами, работа выполняется в течение непрерывного отрезка времени продолжительностью ti, должна быть начата не раньше li, а закончена не позже ri.
Работы Поликарпа обладают удивительным свойством: для любых работ j, k (при j < k) lj < lk и rj < rk.
Пусть имеется упорядоченное множество работ A, содержащее |A| работ. Будем считать, что aj = (lj, rj, tj) (1 ≤ j ≤ |A|). Также будем считать, что работы упорядочены по возрастанию lj с увеличением номера.
Рассмотрим следующую рекурсивную функцию f, аргументом которой является упорядоченное множество работ A, а результатом является целое число. Функция f(A) определяется жадным алгоритмом, которые описан ниже на псевдоязыке программирования.
Поликарп запутался во всех этих формулах и определениях, поэтому он попросил вас промоделировать работу функции f, вычислите значение f(A).
В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 105) — количество работ в множестве A.
Далее в n строках описаны сами работы. В i-й строке записано три целых числа через пробел li, ri, ti (1 ≤ li ≤ ri ≤ 109, 1 ≤ ti ≤ ri - li + 1) — описание i-й работы.
Гарантируется, что для любых работ j, k (при условии j < k) верно, что lj < lk и rj < rk.
Для каждой работы i выведите одно целое число — результат обработки работы i на i-ой итерации цикла (шага 3) в функции f(A). В i-й строке выведите:
5
1 8 5
2 9 3
3 10 3
8 11 4
11 12 2
0 0 1 0 -1
13
1 8 5
2 9 4
3 10 1
4 11 3
8 12 5
9 13 5
10 14 5
11 15 1
12 16 1
13 17 1
14 18 3
15 19 3
16 20 2
0 0 0 2 -1 -1 0 0 0 0 7 0 12
Название |
---|