Fișierul intrare/ieșire | cautbin.in, cautbin.out | Sursă | Infoarena |
---|---|---|---|
Autor | clasică | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.35 sec | Limită de memorie | 5120 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Căutare binară
Se dă un șir de numere ordonat crescător cu N elemente. Se cere să răspundeți la M întrebări de tipul:
- 0 x – cea mai mare poziție pe care se află un element cu valoarea x, sau -1 dacă această valoare nu se găsește în șir
- 1 x – cea mai mare poziție pe care se află un element cu valoarea mai mică sau egală cu x în șir. Se garantează că cel mai mic număr al șirului este mai mic sau egal cu x
- 2 x – cea mai mică poziție pe care se află un element cu valoarea mai mare sau egală cu x în șir. Se garantează că cel mai mare număr din șir este mai mare sau egal cu x
Date de intrare
Pe prima linie a fișierului de intrare cautbin.in se află numărul N reprezentând numărul de elemente ale șirului. Pe următoarea linie se găsesc N numere reprezentănd elementele șirului. Linia a treia conține numărul M reprezentănd numărul de întrebări. Apoi urmează M linii, fiecare cu unul dintre cele 3 tipuri de întrebări.
Date de ieșire
În fișierul de ieșire cautbin.out se vor afișa M linii reprezentând răspunsul la cele M întrebări.
Restricții
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- Elementele șirului vor fi numere strict pozitive și se vor încadra pe 31 de biți
Exemplu
cautbin.in | cautbin.out | Explicație |
---|---|---|
5 1 3 3 3 5 3 0 3 1 3 2 3 |
4 4 2 |
Ultima apariție a numărului 3 în șir este pe poziția 4. Prima apariție pe poziția 2. |