Cod sursa(job #216855)

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

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

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

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

int caut(int x)
{
	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(int x)
{
	int poz = hash_function(x);
	pNod q;
	if (!caut(x))
	{
		q = new nod;
		q -> x = x;
		q -> ap = 1;
		q -> a = hash[poz];
		hash[poz] = q;
		nr++;
	}
	else
	{
		for (q = hash[poz]; q -> x != x; q = q -> a);
		q -> ap++;
	}
}

void sterg(int x)
{
	int poz = hash_function(x);
	pNod q, p;

	for (q = hash[poz]; q -> x != x; q = q -> a);
	q -> ap--;

	if (q -> ap == 0)
	{
		if (hash[poz] -> x == x) hash[poz] = hash[poz] -> a;
		else 
		{
			for (p = hash[poz]; p -> a -> x != x; p = p -> a);
			p -> a = p -> a -> a;
		}
		nr--;
	}

}


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

	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++)
	{
		add(v[i]);
		if (nr >= l)
			while (nr >= l)
			{
				j++;
				sterg(v[j]);
			}
		rez1 += j;
	}

	for (i = 1; i <= n; i++) hash[i] = NULL;

	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("%d\n",rez);
	return 0;
}