Fişierul intrare/ieşire:cautbin.in, cautbin.outSursăInfoarena
AutorclasicaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.25 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.incautbin.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici