Cod sursa(job #9883)

Utilizator victorsbVictor Rusu victorsb Data 27 ianuarie 2007 18:46:57
Problema Secventa 5 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 65536

unsigned int sir[Nmax], n, l, u, i, j, k, ind[Nmax], inv[Nmax], v[Nmax], ct;
long long sol;

void citire()
{
    scanf("%lld %lld %lld\n", &n, &l, &u);
    for (i=1; i<=n; ++i)
        scanf("%lld\n", &sir[i]);
}

int cmp(const int a, const int b)
{
    return sir[a] < sir[b];
}

void solve()
{
    for (i=1; i<=n; ++i)
        ind[i] = i;
    sort(ind + 1, ind + n + 1, cmp);
    for (i=1; i<=n; ++i)
        inv[ind[i]] = i;
    for (i=1; i<=n; ++i)
        if (sir[ind[i]] == sir[ind[i-1]])
            inv[ind[i]] = inv[ind[i-1]];
    for (i=1; i<=n; ++i)
    {
        ct = 0;
        for (j=i; j<=n; ++j)
        {
            if (v[inv[j]] == 0)
                ct++;
            v[inv[j]]++;
            if (l <= ct && ct <= u)
                sol++;
            if (ct > u)
                break;
        }
        for (k=i; k<=j; ++k)
            v[inv[k]] = 0;
    }
    printf("%lld\n", sol);
}

int main()
{
    freopen("secv5.in","r",stdin);
    freopen("secv5.out","w",stdout);
    citire();
    solve();
    return 0;
}