Fişierul intrare/ieşire:kami.in, kami.outSursăAlgoritmiada 2014, Runda 1
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Kami

Pe muntele din Athos 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.inkami.out
5
10 4 1 2 3
4
1 4
1 5
0 1 9
1 5
2
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content