Cod sursa(job #3128380)

Utilizator oana75Ioana Prunaru oana75 Data 9 mai 2023 14:05:57
Problema Secventa 5 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstring>

using namespace std;
const int NMAX = 1100000;

struct elem
{
    int val, ind;
};

int N, L, U, b[NMAX], fr[NMAX];
elem V[NMAX];

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

inline bool cmp(elem A, elem B)
{
    return A.val < B.val;
}

void normalizare()
{
    sort(V + 1, V + 1 + N, cmp);
    int crt = 1;
    b[V[1].ind] = 1;
    for(int i = 2; i <= N; i++)
    {
        if(V[i].val > V[i - 1].val)
            crt++;
        b[V[i].ind] = crt;
    }
}

long long secvente(int b[], int L, int U)
{
    long long nr = 0;
    for(int i = 1; i <= N; i++)
    {
        int dist = 0;
        memset(fr, 0, sizeof(fr));
        for(int j = i; j <= N; j++)
        {
            fr[b[j]]++;
            if(fr[b[j]] == 1)
                dist++;
            if(dist >= L && dist <= U)
                nr++;
            if(dist > U)
                break;
        }
    }
    return nr;
}

int main()
{
    in >> N >> L >> U;
    for(int i = 1; i <= N; i++)
    {
        in >> V[i].val;
        V[i].ind = i;
    }
    normalizare();
    out << secvente(b, L, U);
    in.close();
    out.close();
    return 0;
}