Cod sursa(job #14664)

Utilizator wefgefAndrei Grigorean wefgef Data 9 februarie 2007 13:29:10
Problema Secventa 5 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

#define Nmax (1 << 20)

int x[Nmax], u[Nmax], v[Nmax];
int frec[Nmax];
int n, m, a, b;

void readdata()
{
	freopen("secv5.in", "r", stdin);
	freopen("secv5.out", "w", stdout);
	
	scanf("%d %d %d", &n, &a, &b);
	for (int i = 0; i < n; ++i)
	{
		scanf("%u", &u[i]);
		x[i] = i;
	}
}

long long eval(int k)
{
	int i, j = 0, cnt = 0;
	long long rez = 0;
	
	if (k == a-1) memset(frec, 0, sizeof(frec));
	for (i = 0; i < n; ++i)
	{
		cnt += ++frec[v[i]] == 1;
		
		while (cnt > k)
			if (--frec[v[j++]] == 0) --cnt;

		rez += i-j+1;
	}
	return rez;
}

int inline cmp(int a, int b)
{
	return u[a] < u[b];
}

void solve()
{
	int i;
	
	sort(x, x+n, cmp);
	
	v[ x[0] ] = 0;
	for (i = 1; i < n; ++i)
	{
		if (u[x[i]] > u[x[i-1]]) ++m;
		v[ x[i] ] = m;
	}
	
	printf("%lld\n", eval(b) - eval(a-1));
}

int main()
{
	readdata();
	solve();
	return 0;
}