Cod sursa(job #2039012)

Utilizator trifangrobertRobert Trifan trifangrobert Data 14 octombrie 2017 10:34:11
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>

#include <fstream>
#include <map>

using namespace std;

map <unsigned, int> M;
unsigned a[1024 * 1024 + 20];
int n, l, u;

///cate secvente au cel mult k valori distincte
long long NrSecvente(int k)
{
    long long cnt = 0;
    int i, j;
    unsigned x;
    i = 1;
    for (j = 1;j <= n;++j)
    {
        M[a[j]]++;
        while(M.size() > k)
        {
            cout << i << " ";
            x = a[i];
            ++i;
            M[x]--;
            if (M[x] == 0)
                M.erase(x);
        }
        cnt += (j - i + 1);
        ///adaug cele j - i + 1 secvente care se termina cu a[j];

    }
    return cnt;
}

void Read()
{
    ifstream f("secv5.in");
    f >> n >> l >> u;
    for (int i = 1;i <= n;++i)
        f >> a[i];
    f.close();
}

int main()
{
    Read();
    ofstream g("secv5.out");
    g << NrSecvente(u) - NrSecvente(l - 1) << "\n";
    g.close();
    return 0;
}