Fişierul intrare/ieşire:pinball.in, pinball.outSursăONIS 2015, Runda 1
AutorMihai NituAdăugată deThe_Viper_The_Mountain_And_The_ImpUNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test1.9 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Por Costel si Pinball

Por Costel se joaca pinball. Dupa multe ore de studiat jocul prin lovituri repetate ale mesei de pinball cu ratul, Por Costel crede ca s-a prins cum functioneaza.

Exista N spring-uri pe masa de pinball, care au rolul de a lansa bila mai departe. Imaginandu-ne o vedere “de sus” a mesei, springul i este al i-lea spring de la stanga la dreapta, adica pe orizontala. Acum, spring-urile sunt caracterizate si de pozitia lor pe verticala. Anume, al i-lea spring are o coordonata verticala v_i.

Daca bila se loveste de un spring i, acesta o lanseaza catre un alt spring j, j > i. Spunem, in acest caz, ca bila ricoseaza din spring-ul i in spring-ul j. Exista doua posibilitati:

  • ricosare in sus: v_j > v_i, numai daca ultima ricosare a fost in jos.
  • ricosare in jos: v_j < v_i, numai daca ultima ricosare a fost in sus.

Prima ricosare nu are nicio restrictie: Por Costel lanseaza bila catre primul spring, iar din acesta ea ricoseaza fie in sus fie in jos. Punctajul pe care il obtine Por Costel la o lansare este numarul de spring-uri din care ricoseaza bila. O data ce ea a trecut de ultimul spring, tura s-a terminat.

Por Costel a petrecut foarte mult timp calculand punctajul maxim pe care il poate obtine lansand bila corect. Insa, ce nu stie el e ca faptul ca loveste masa din cand in cand face ca unele spring-uri sa-si modifice coordonata verticala v_i. Ajutati-l pe Por Costel sa calculeze in fiecare moment punctajul maxim pe care il poate obtine.

Date de intrare

Fişierul de intrare pinball.in va contine pe prima linie numarul N. A doua linie va contine un sir de N numere intregi v. A treia linie va contine numarul M iar urmatoarele M linii vor contine cate doua numere x si y reprezentand o modificare astfel: spring-ul x capata coordonata verticala y (v_x = y)

Date de ieşire

În fişierul de ieşire pinball.out se vor afla M+1 linii. Prima linie contine raspunsul pentru starea initiala a vectorului. Apoi, avem M linii cu raspunsul dupa fiecare din cele M modificari.

Restricţii

  • 1N, M10^6
  • 1v_i, y10^9
  • 1xN
  • Se garanteaza ca nu vor exista i si j astfel incat v_i = v_j atat in sirul initial cat si pe parcursul celor M operatii

Exemplu

pinball.inpinball.out
10
1 10 2 5 6 3 4 8 9 7
3
1 11
7 17
8 12
7
6
8
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content