Fişierul intrare/ieşire: | trade.in, trade.out | Sursă | ad-hoc |
Autor | Adăugată de | ||
Timp execuţie pe test | 1.1 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile 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 |