Fișierul intrare/ieșire trade.in, trade.out Sursă ad-hoc
Autor Adăugată de avatar mihai995 Andreescu Mihai mihai995
Timp de execuție pe test 1.1 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii