Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | expanding.in, expanding.out | Sursă | Junior Challenge 2025 |
| Autor | Muresan Luca Valentin | Adăugată de |  andrei iorgulescu •andreiiorgulescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Expanding
În Ţinutul Ooo, Finn şi Jake descoperă un şir magic de pietre strălucitoare aşezate în linie.
Fiecare piatră are o valoare, valori pe care le vom reprezenta cu un şir a de n elemente.
În mod important, nu există trei pietre care să aibă aceeaşi valoare.
Încercând să colecteze toate pietrele, cei doi se vor mişca după următoarele reguli:
Ei pornesc de la o poziţie p, cu o poţiune de putere c = a[p].
La un pas, ei se pot muta doar într-o poziţie adiacentă; dacă aceasta există în şir, poate fi vizitată sau nu anterior.
Pentru un ban, ei pot schimba puterea poţiunii c la orice valoare pozitivă.
O mutare într-o poziţie vizitată este mereu posibilă şi nu are niciun efect.
Pentru a vizita o poziţie nevizitată, trebuie ca puterea poţiunii c să fie egală cu valoarea poziţiei în care merg.
Când ajung într-o poziţie nouă, ei colectează piatra din acea poziţie.
Definim f(p) ca fiind numărul minim de bani de care au nevoie cei doi pentru a putea colecta toate pietrele, dacă pornesc în poziţia p cu c = a[p].
Vi se dau n, şirul a de n elemente şi q query-uri; pentru fiecare query primiţi o poziţie p şi trebuie să afişaţi f(p).
h2. Date de intrare
Fişierul de intrare expanding.in conţine pe prima linie numărul n, urmat pe a doua linie de şirul a.
Pe a treia linie se găseşte q, urmat de q linii cu câte un număr, valorile p ale query-urilor.
Date de ieşire
În fişierul de ieşire expanding.out afişaţi q linii, pe linia i afişând răspunsul de la al i-lea query.
Restricţii
- 1 ≤ n ≤ 1 000 000
- 1 ≤ ai ≤ n
- 1 ≤ q ≤ 1 000 000
- 1 ≤ p ≤ n
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 10 | n ≤ 500 şi q ≤ 500 |
| 2 | 10 | n ≤ 5000 şi q ≤ 10 |
| 3 | 15 | n ≤ 5000 şi q ≤ 5000 |
| 5 | 15 | n ≤ 100 000 şi q ≤ 10 |
| 5 | 25 | n ≤ 100 000 şi q ≤ 100 000 |
| 6 | 25 | n ≤ 1 000 000 şi q ≤ 1 000 000 |
Exemplu
| sandwich.in | sandwich.out |
|---|---|
| 8 2 1 3 4 6 3 2 1 8 1 2 3 4 5 6 7 8 | 7 6 6 5 5 6 6 7 |
Explicaţie
🤡🤡🤡
