Fişierul intrare/ieşire:ismquery.in, ismquery.outSursă.com 2012 Runda 1
AutorMihai PopaAdăugată deedp100Edp100 edp100
Timp execuţie pe test0.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ismquery

Bluff a descoperit recent in masina portocalie un sir A de N numere intregi. Instant, i-au venit in cap M intrebari de forma: dandu-se o pozitie p a sirului si un numar k, sa se afiseze a k-a pozitie notata r din dreapta pozitiei p (r > p) cu proprietatea ca Ar > Ap.
Bluff isi genereaza intrebarile in felul urmator, cunoscand valorile G si H:
pi = 1 + (i + pi-1*G)%N
ki = 1 + (i + ki-1*H)%5

Date de intrare

Fişierul de intrare ismquery.in va contine pe prima linie doua numere naturale N si M cu semnificatia din enunt. A doua linie va continue N numere separate prin spatii, reprezentand continutul sirului A. Linia 3 va contine numerele G respectiv H, separate prin spatiu, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire ismquery.out vor fi afisate M linii, fiecare continand raspunsul la cate o intrebare in ordinea generarii lor. Daca pentru un query pozitia ceruta nu exista, se va afisa 0.

Restricţii

  • N ≤ 400.000
  • M ≤ 1.200.000
  • p0 = k0 = 1
  • Evident, ki ≤ 5 pentru orice 1 ≤ i ≤ M
  • -2.000.000.000 ≤ Ai ≤ 2.000.000.000 pentru orice 1 ≤ i ≤ N
  • Elementele sirului A si cele M intrebari se numeroteaza incepand cu 1
  • 1 ≤ G,H ≤ 1000

Exemplu

ismquery.inismquery.out
9 3
4 5 -1 7 2 5 2 9 3
1 1
6
8
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content