Cod sursa(job #9593)

Utilizator sims_glAlexandru Simion sims_gl Data 27 ianuarie 2007 16:21:30
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Unirea 2007, clasele 11-12 Marime 1.06 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 1050000

int n, m, x, y, a[nm], b[nm], c[nm];
long long sol;

int comp(int p, int r)
{
	return a[b[p]] < a[b[r]];
}

int main()
{
	int i, j, crt;

	freopen("secv5.in", "r", stdin);
    freopen("secv5.out", "w", stdout);

	scanf("%d%d%d", &n, &x, &y);

    for (i = 1; i <= n; ++i)
    {
    	scanf("%d", &a[i]);
    	b[i] = i;
    }

    sort(b + 1, b + n + 1, comp);

    for (crt = 1, i = 1; i <= n; ++i)
    {
    	if (i > 1 && a[b[i]] != a[b[i - 1]])
        	++crt;

        c[i] = crt;
    }

    for (i = 1; i <= n; ++i)
    	a[b[i]] = c[i];

    for (i = 1; i <= n; ++i)
    {
    	for (m = 0, j = 1; j <= n; ++j)
        	c[j] = 0;
            
	    for (j = i; j <= n; ++j)
        {
            ++c[a[j]];
            if (c[a[j]] == 1)
            	++m;
        	if (m >= x && m <= y)
            	sol = (long long)sol + 1;
            else if (m > y)
            	break;
        }
    }

    printf("%lld\n", sol);
    
	return 0;
}