Fișierul intrare/ieșire	incrementmax.in, incrementmax.out	Sursă	Codility
Autor	autor necunoscut	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	1.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Increment & Max

Dacă tot am vorbit de curând despre tehnica împarte și cucerește, cred că este momentul să descoperim și tehnica incrementează și “maxează”.

Se dă un vector V cu N elemente, numerotate de la 1 la N. Inițial toate elementele vectorului sunt egale cu zero. Asupra vectorului se aplică Q operații de două tipuri:

• 1 X Y: Valoarea de pe poziția X este incrementată cu Y.
• 2: Toate valorile din vector devin egale cu valoarea maximă.

Date de intrare

Fișierul de intrare incrementmax.in conține pe prima linie numerele N și Q, separate printr-un spațiu. Pe fiecare din următoarele Q linii se va găsi câte o operație din cele Q, sub forma prezentată în enunț.

Date de ieșire

Fișierul de ieșire incrementmax.out va conține o singură linie, pe care vor fi scrise cele N valori din vectorul V, separate între ele prin câte un spațiu.

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ Q ≤ 100.000
• Se garantează că în toate operațiile de tip 1, 1 <= X <= N și 1 <= Y <= 20.000
• Pentru 40% dintre teste: 1 <= N <= 1.000 și 1 <= Q <= 1.000

Exemplu

Explicație

Vectorul după fiecare operație în parte:

0. [0, 0, 0, 0, 0]
1. [0, 0, 1, 0, 0]
2. [0, 0, 2, 0, 0]
3. [0, 1, 2, 0, 0]
4. [2, 2, 2, 2, 2]
5. [2, 2, 2, 2, 3]
6. [3, 3, 3, 3, 3]
7. [4, 3, 3, 3, 3]