Fișierul intrare/ieșire cautbin.in, cautbin.out Sursă Infoarena
Autor clasică Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.35 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii