# PBinfo #2276 – cb – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y. 

Cerința
Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare
Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire
Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare.

Restricții și precizări

1 ≤ n, T ≤ 200 000
0 ≤ a[i] ≤ 2 000 000 000
0 ≤ x ≤ y ≤ 2 000 000 000

Exemplu:
Intrare

9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9
Ieșire

4
9
1
0
3
0
7

## Cod sursă C++

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int v[200003], n;
int cb1(int x) {
    if (v[n] < x) return n + 1;
    if (x <= v[1]) return 1;
    int stanga, dreapta, mijloc, p;
    stanga = 1; dreapta = n; p = 1;
    while (stanga <= dreapta) {
    	mijloc = (stanga + dreapta) / 2;
        if (x <= v[mijloc]) {
            p = mijloc; dreapta = mijloc - 1;
        } else stanga = mijloc + 1;
    } return p;
}
int cb2(int y) {
    if (v[n] <= y) return n;
    if (v[1] > y) return 0;
    int stanga, dreapta, mijloc, p;
    stanga = 1; dreapta = n; p = 1;
    while (stanga <= dreapta) {
    	mijloc = (stanga + dreapta) / 2;
        if (v[mijloc] <= y) {
            p = mijloc; stanga = mijloc + 1;
        } else dreapta = mijloc - 1;
    } return p;
}
int main() {
    int i, p, q, T, x, y;
    cin >> n >> T;
    for (i = 1; i <= n; i++)
        cin >> v[i];
    sort(v + 1, v + n + 1);
    while (T--) {
        cin >> x >> y;
        p = cb1(x);
        q = cb2(y);
        cout << (q - p + 1) << "\n";
    } return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2276)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2276/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2276/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)