Cod sursa(job #217952)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 30 octombrie 2008 23:11:31
Problema Secventa 5 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <string.h>

unsigned int n, l, u, v[1500000], nr, rez1, rez2, rez;

unsigned int hash[2700000], viz[2700000];

unsigned int hash_function(unsigned int x)
{
	unsigned int y = x % 2666013;
	while (hash[y] && (hash[y] != x)) y++;
	hash[y] = x;
	return y;
}

unsigned int caut(unsigned int x)
{
	unsigned int xx = hash_function(x);
		if (viz[xx]) return 1;
	return 0;
}

void add(unsigned int x)
{
	unsigned int poz = hash_function(x);	
	if (!caut(x))
	{
		viz[poz]++;
		nr++;
	}
	else viz[poz]++;
}

void sterg(unsigned int x)
{
	unsigned int poz = hash_function(x);
	viz[poz]--;
	if (!viz[poz]) nr--;
}


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

	unsigned int i, j;
	char s[100];

	scanf("%u %u %u\n",&n,&l,&u);

	for (i = 1; i <= n; i++)
	{
		scanf("%s",s);
		j = 0;
		while (s[j] <= '9' && s[j] >= '0')	v[i] = v[i] * 10 + s[j++] - '0';
	}
}

int main()
{
	citire();
	unsigned int i, j;

	j = 0;
	for (i = 1; i <= n; i++)
	{
		add(v[i]);
		if (nr >= l)
			while (nr >= l)
			{
				j++;
				sterg(v[j]);
			}
		rez1 += j;
	}

	nr = 0;
	j = 0;
	for (i = 1; i <= n; i++)
	{
		add(v[i]);
		if (nr >= u + 1)
			while (nr >= u + 1)
			{
				j++;
				sterg(v[j]);
			}
		rez2 += j;
	}

	rez = rez1 - rez2;
	printf("%u\n",rez);
	return 0;
}