Cod sursa(job #10953)

Utilizator vlad_DVlad Dumitriu vlad_D Data 30 ianuarie 2007 03:04:20
Problema Secventa 5 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
/*
by vlad D.
   :)
*/
#include <cstdio>
#include <map>
#include <time.h>
#include <stdlib.h>
using namespace std;
unsigned int ret;
unsigned int N, A, B;
unsigned int aha[1048590];
unsigned int i, j;
int M = 2*497719;
int sol[1000000], unde[1048590];
map<unsigned int, int> Q;
int main() {
	freopen("secv5.in", "r", stdin);
	freopen("secv5.out", "w", stdout);
	scanf("%u %u %u", &N, &B, &A);
	srand(time(0)%123);
	int R = rand()%9999;
	if (R <=3 )  R = 237;
	int pas = 0;
	for (i=1; i<=N; i++) {
		unsigned int X;
		scanf("%u", &X);
		int XX = X;
		XX*=R;
		XX%=M;
		if (sol[XX]==0) {pas++; sol[XX] = pas;}
		aha[i] = sol[XX];
		}
	//Q.clear();
	int cate = 0;
	int last = 1;
	for (i=1; i<=N; i++) {
		unde[aha[i]]++; if (unde[aha[i]] == 1) cate++;
		while (cate > A) {unde[aha[last]]--; if (unde[aha[last]] == 0) cate--; last++;}
		ret+= 1+ i - last ;
		}
	B--;
	last = 1, cate = 0;
	for (i=1; i<=pas; i++) unde[i] = 0;
	if (B>0)
		for (i=1; i <=N; i++) {
		unde[aha[i]]++; if (unde[aha[i]] == 1) cate++;
		while (cate > B) {unde[aha[last]]--; if (unde[aha[last]] == 0) cate--; last++;}
		ret-= i+1 - last;
		}
	printf("%u\n", ret);
	return 0;
}