Cod sursa(job #2038985)

Utilizator loo_k01Luca Silviu Catalin loo_k01 Data 14 octombrie 2017 10:29:30
Problema Secventa 5 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

int a[1024 * 1024 + 20], n, L, U;

///cate secvente au cel mult k valori distincte
unsigned long long NrSecvente(unsigned int K)
{
    unordered_map <unsigned, int> m;
    long long cnt = 0, j = 1;

    for(int i = 1; i <= n; i++)
    {
        m[a[i]]++;
        while(m.size() > K)
        {
            m[a[j]]--;
            if(m[a[j]]==0)
                m.erase(a[j]);
            j++;
        }
        cnt += (i - j + 1);
    }
    return cnt;
}

void Read()
{
    ifstream fin("secv5.in");
    fin >> n >> L >> U;

    for(int i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
}

int main()
{
    Read();
    ofstream fout("secv5.out");
    fout << NrSecvente(U) - NrSecvente(L - 1) << "\n";
    return 0;
}