# PBinfo #4300 – secv_fb – Rezolvare C++

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

## Enunț

Cerința
Se citește un număr N, un număr K și apoi un șir cu N numere naturale. Determinați câte secvențe de lungime exact K au elementele distincte. Prin secvență înțelegem un set de elemente aflate pe poziții consecutive.

Date de intrare
Pe prima linie a fișierului secv_fb.in se găsesc două numere naturale, separate prin exact un spațiu, N și K. Pe linia a doua se găsesc cele N numere ale șirului, separate prin câte un spațiu.

Date de ieșire
Pe prima linie a fișierului secv_fb.out se găsește un număr natural ce reprezintă valoarea cerută.

Restricții și precizări

2 ≤ N ≤ 100.000;
Pentru 20 de puncte K = 2;
Pentru alte 20 de puncte K = 3;
Pentru alte 20 de puncte 4 ≤ K ≤ 10;
Pentru alte 20 de puncte, 10 < K ≤ n-1 și valorile din șir ≤ 100.000;
Pentru restul testelor 10 < K ≤ n-1 și valorile din șir ≤ 2.000.000.000;

Exemplu:
secv_fb.in

8 3
3 2 4 3 4 5 6 7
secv_fb.out

5

## Cod sursă C++

```cpp
#include <fstream>
#include <algorithm>
using namespace std;
int v[100010], w[100010], p[100010], f[100010];
int n, k, i, st, dr, mid, sol, rep;
int main () {
    ifstream fin ("secv_fb.in");
    ofstream fout("secv_fb.out");
    fin>>n>>k;
    for (i=1;i<=n;i++) {
        fin>>v[i];
        w[i] = v[i];
    }
    sort(w+1, w+n+1);
    p[1] = 1;
    for (i=2;i<=n;i++)
        if (w[i] == w[i-1])
            p[i] = p[i-1];
        else
            p[i] = 1+p[i-1];
    for (i=1;i<=n;i++) {
        st =1; dr = n;
        while (st <= dr) {
            mid = (st + dr)/2;
            if (w[mid] == v[i]) {
                v[i] = p[mid];
                break;
            }
            if (v[i] < w[mid])
                dr = mid - 1;
            else
                st = mid + 1;
        }
    }
    for (i=1;i<=n;i++) {
        f[ v[i] ]++;
        if (f[ v[i] ] == 2)
            rep++;
        if (i>k) {
            f[ v[i-k] ]--;
            if ( f[ v[i-k] ] == 1)
                rep--;
        }
        if (i >= k && rep == 0)
            sol++;
    }
    fout<<sol<<"\n";
    return 0;
}
```

## Resurse

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