# PBinfo #4265 – perechiAB – Rezolvare C++

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

## Enunț

Se dă un șir v1, v2, …, vn de numere naturale nenule și de asemenea se dau două numere naturale nenule A și B.

Cerința
Să se determine numărul perechilor (vi , vj) cu i < j și A ≤ vi + vj ≤ B.

Date de intrare
Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații, iar la final se citesc numerele naturale nenule A și B.

Date de ieșire
Programul va afișa pe ecran numărul de perechi care îndeplinesc condițiile cerute.

Restricții și precizări

3 ≤ n ≤ 160.000
1 ≤ A ≤ B ≤ 2.000.000.000
1 ≤ vi ≤ 1.000.000.000

Exemplu:
Intrare

5
1 2 3 4 5
7 10
Ieșire

4
Explicație
Perechile sunt: (2, 5), (3, 4), (3, 5), (4, 5).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[160005];
/// cea mai din dreapta pozitie p cu val + a[p] <= X
int CautBin(int j, int val, int X)
{
    if (val + a[n] <= X) return n;
    if (val + a[j] > X) return -1;
    int st, dr, mij, p;
    st = j; dr = n;
    p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (val + a[mij] <= X)
        {
            p = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return p;
}
int main()
{
    int i, j, A, B;
    long long cnt = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> A >> B;
    sort(a + 1, a + n + 1);
    /// cate perechi au suma a[i]+a[j] <= B
    for (i = 1; i < n; i++)
    {
        j = CautBin(i + 1, a[i], B);
        if (j != -1) cnt += (j - i);
    }
    /// cate perechi au suma a[i]+a[j] <= A - 1
    for (i = 1; i < n; i++)
    {
        j = CautBin(i + 1, a[i], A - 1);
        if (j != -1) cnt -= (j - i);
    }
    cout << cnt << "\n";
    return 0;
}
```

## Resurse

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