Cod sursa(job #2764310)

Utilizator marcumihaiMarcu Mihai marcumihai Data 20 iulie 2021 13:00:45
Problema Secventa 5 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("secv5.in");
ofstream g ("secv5.out");

int n;
int v[1000005];
vector <int> a;
int ordine[1000005];
int st, dr;
int L[1000005];
int fr[1000005];
int rez (int x)
{
    int cont=0;
    for(int i=0; i<=n; ++i)
    {
        L[i]=0;
        fr[i]=0;
    }
    int j=1;
    for(int i=1; i<=n; ++i)
    {
        if(fr[v[i]]==0)
            ++cont;
        fr[v[i]]++;

        while(cont>x && j<=i)
        {
            if(fr[v[j]]==1)
            {
                --cont;
            }
            --fr[v[j]];
            ++j;
        }
        L[i]=j;



    }
    int sum=0;
    for(int i=1; i<=n; ++i)
        sum+=i-L[i]+1;
    return sum;
}


int main()
{
    f>>n>>st>>dr;
    for(int i=0; i<n; ++i)
    {
        int x;
        f>>x;
        a.push_back(x);
    }

    map<int, int> M;
    for (int i = 0; i < a.size(); i++)
        M[a[i]];
    int pt = 0;
    for (map<int, int>::iterator it = M.begin(); it != M.end(); it++)
        it->second = pt++;
    for (int i = 0; i < a.size(); i++)
        a[i] = M[a[i]];
    for(int i=0; i<a.size(); ++i)
        v[i+1]=a[i];

    g<<rez(dr)-rez(st-1);
    return 0;
}