| Fişierul intrare/ieşire: | ismquery.in, ismquery.out | Sursă | .com 2012 Runda 1 |
| Autor | Mihai Popa | Adăugată de |  Edp100 •edp100 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ismquery.out |
|---|---|
| 9 3 4 5 -1 7 2 5 2 9 3 1 1 | 6 8 0 |
