Cod sursa(job #216821)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 25 octombrie 2008 22:19:26
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <string.h>

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

typedef struct nod
{
	unsigned int x;
	nod *a;
} *pNod;
pNod hash[700000];

unsigned int hash_function(unsigned int x)
{
	return x % 666013;
}

unsigned int caut(unsigned int x)
{
	unsigned int xx = hash_function(x);
	for (pNod p = hash[xx]; p != NULL; p = p -> a)
		if (p -> x == x) return 1;
	return 0;
}

void add(unsigned int x)
{
	unsigned int poz = hash_function(x);
	pNod q = new nod;
	q -> x = x;
	q -> a = hash[poz];
	hash[poz] = q;
}

void sterg(unsigned int x)
{
	unsigned int poz = hash_function(x);
	pNod q;
	if (hash[poz] -> x == x) hash[poz] = hash[poz] -> a;
	else
	{
		for (q = hash[poz]; q -> a -> x != x; q = q -> a);
		q -> a = q -> a -> a;
	}
}


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

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

	scanf("%d %d %d\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();
	int i, j;

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

	memset(viz,0,sizeof(viz));
	nr = 0;
	j = 0;
	for (i = 1; i <= n; i++)
	{
		if (caut(v[i])) viz[ v[i] ]++;
		else
		{
			viz[ v[i] ]++;
			nr++;
			add(v[i]);
			if (nr >= u + 1)
				while (nr >= u + 1)
				{
					j++;
					if (viz[v[j]] > 1) viz[v[j]]--;
					else 
					{
						viz[v[j]]--;
						sterg(v[j]);
						nr--;
					}
				}
		}
		rez2 += j;
	}

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