e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

ADA University - March 7 - Segment Tree

Торговля

Вдоль трассы Алматы-Тараз есть n населенных пунктов, пронумерованных числами от 1 до n. В начале зимы m неизвестных торговцев привезли из неизвестного аула вязаные шапки и начали ими торговать в этих населенных пунктах. У этих торговцев есть два принципа: не торговать в одном месте более одного раза (один день) и с каждым днем увеличивать цену на шапку.

Более формально каждый i-ый торговец:

  • Начинает торговать в населенном пункте li со стартовой ценой на одну шапку xi
  • Каждый день переходит в соседний населенный пункт, то есть, если вчера он торговал в населенном пункте j, то сегодня торгует в населенном пункте j + 1
  • Каждый день увеличивает цену на 1, то есть, если вчера цена на его шапки была x, то сегодня цена x + 1
  • Завершает торговать в населенном пункте ri (при этом в пункте ri торговля происходит).

Наша задача для каждого населенного пункта определить максимальную цену на одну шапку за всю историю.

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

В первой строке находятся два целых числа n (1n300000) и m (1m300000) количество населенных пунктов и количество торговцев соответственно.

В каждой из следующих m строк находятся по три целых числа li, ri (1 ≤ lirin) и xi (1xi109) - номера начального и конечного населенных пунктов и начальная цена на шапку для i-го торговца соответственно.

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

Выведите n целых чисел, разделенных пробелом,  где i-ое число равно максимальной цене на одну шапку за всю историю продаж i-ого населенного пункта. Если в каком-то населенном пункте никто не торговал шапками, то для этого населенного пункта выведите 0.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
5 2
1 3 2
2 4 6
Çıxış verilənləri #1
2 6 7 8 0
Giriş verilənləri #2
6 4
4 4 3
1 2 5
5 6 1
6 6 1
Çıxış verilənləri #2
5 6 0 3 1 2
Mənbə 2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января