| Fişierul intrare/ieşire: | kami.in, kami.out | Sursă | Algoritmiada 2014, Runda 1 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Kami
Pe muntele din Athos Olimp se afla N nivele. Pentru fiecare nivel se cunoaste cantitatea de zapada zi aflata acolo. Zeus poate sa dea cu fulgerul pe un nivel si sa provoace o avalansa care porneste de acolo. Fenomenul de avalansa dintr-un nivel i se desfasoara in felul urmator: zapada de pe nivelul i coboara pe nivelul i - 1. Daca cantitatea de zapada de pe nivelul i - 1 este mai mare sau egala decat cantitatea de zapada de pe nivelul i, atunci avalansa se opreste. Daca nu, cantitatile de zapada se aduna si avalansa continua mai departe cu un nivel mai jos. Se dau M operatii de 2 tipuri:
0 x val - Poseidon schimba valoarea de pe nivelul x cu val
1 b - Athena vrea sa stie daca Zeus ar da cu fulgerul in nivelul b si ar provoca o avalansa de acolo, care ar fi nivelul a in care s-ar opri avalansa?
Date de intrare
Fişierul de intrare kami.in va contine pe prima linie N. Pe linia 2 vor fi N numere naturale reprezentand zi. Pe linia 3 va fi M iar pe urmatoarele M linii cele M operatii.
Date de ieşire
Fişierul de ieşire kami.out va contine cate un raspuns pentru fiecare intrebare data de Athena reprezentand pozitia unde se opreste avalansa. Daca avalansa nu se opreste nici macar in pozitia 1, consideram ca se opreste in 0.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 100.000
- 1 ≤ zi ≤ 1.000.000.000
Exemplu
| kami.in | kami.out |
|---|---|
| 5 10 4 1 2 3 4 1 4 1 5 0 1 9 1 5 | 2 1 0 |
