# PBinfo #3939 – Intervale6 – Rezolvare C++

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

## Enunț

Cerința
Se dă un șir n numere naturale separate prin câte un spațiu.
Se cere să se afișeze numărul de intervale care nu conțin niciun termen al șirului.

Date de intrare
Fișierul de intrare intervale6.in conține: 

pe prima linie un număr n.
pe a doua linie un șir de n numere.
iar pe fiecare dintre următoarele linii, până la finalul fișierului, câte o pereche de numere, reprezentând extremitățile unui interval închis.


Date de ieșire
Fișierul de ieșire intervale6.out va conține numărul de intervale care nu conțin niciun termen al șirului aflat pe a doua linie a fișierului.

Restricții și precizări

Fișierul intervale6.in conține numere naturale din intervalul [1, 10.000].
Numerele aflate pe a doua linie a fișierului sunt în ordine crescătoare.
Vor fi cel mult 200.000 de intervale.

Exemplu:
intervale6.in

5
4 8 9 16 25
1 3
2 5
9 15
5 7
20 100
10 12
intervale6.out

3
Explicație
Intervalele [1, 3], [5, 7], [10, 12] nu conțin niciun termen al șirului 4, 8, 9, 16, 25.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
ifstream fin("intervale6.in");
ofstream fout("intervale6.out");
int v[10001];
int n, x, y, st, dr, mij, ans, ct;
int main() {
    fin >> n;
    for(int i = 1;i <= n;i++) 
        fin >> v[i];
    while(fin >> x >> y) {
        st = 1, dr = n;
        ans++;
        while(st <= dr) {
            mij = (st + dr) / 2;
            if(v[mij] >= x && v[mij] <= y) dr = st - 1, ct++;
            else if(v[mij] > y) dr = mij - 1;
            else if(v[mij] < x) st = mij + 1;
        }
    }
    fout << ans - ct;
    return 0;
}
```

## Resurse

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