Fișierul intrare/ieșire | trade.in, trade.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Adăugată de | Andreescu Mihai • mihai995 | |
Timp de execuție pe test | 1.1 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Trade
O regiune nordică s-a deschis recent comerțului liber. M negustori au decis să profite de această oportunitate și au decis să-și vândă produsele în N dintre orașele acestei regiuni. Orașele sunt așezate de-a lungul unui râu, în linie dreaptă, iar orașele sunt numerotate în ordine, de la 1 la N. Fiecare negustor își alege un interval [ai ; bi] de orașe în care va vinde un produs (unic – fiecare negustor are un produs unic). În plus, ei încep a-și vinde produsele de la prețul pi în orașul ai, dar pe măsură ce înaintează, devine mai lacom și crește prețul cu 1. Cu alte cuvinte, în orașul a va vinde cu p, în orașul a + 1 cu p + 1, … , iar în orașul b cu b – a + p.
Pentru a afla care e cel mai “de fiță” oraș, locuitorii vor să determine pentru orașul lor cât va costa cel mai scump produs adus de negustori. Pentru că ei nu știu să determine acest lucru, vă roagă să-I ajutați.
Date de intrare
În fișierul trade.in se vor găsi N și M, reprezentând numărul de orașe, respectiv numărul de negustori. Pe următoarele M linii, se vor afla câte 3 numere, a, b și p, reprezentând faptul că un negustor se extinde în intervalul [a ; b] și începe în orașul a cu prețul p.
Date de ieșire
În fișierul trade.out se vor găsi N numere. Al i-lea număr va reprezenta prețul celui mai scump produs din orașul i.
Restricții
- 1 <= N<= 1 000 000
- 1 <= M <= 300 000
- 1 <= a < b <= N
- 1 <= p <= 1 000 000 000
- Dacă într-un oraș nu vine niciun negustor, prețul pentru acel oraș va fi 0.
- Pentru 30% din teste, N, M <= 5 000
- Pentru alte 50% din teste, N <= 300 000
Exemplu
trade.in | trade.out |
---|---|
5 2 1 3 2 2 4 6 |
2 6 7 8 0 |
6 4 4 4 3 1 2 5 5 6 1 6 6 1 |
5 6 0 3 1 2 |