Cod sursa(job #496004)

Utilizator ZethpixZethpix Zethpix Data 27 octombrie 2010 16:08:14
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

struct hash
{
	int nod;
	hash *link;
}*H[1000000];

long m,n,a,b,x,d[1100000],e[1100000],v[1100000],i,j,sol;

void add(long x)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->link=H[x%m];
	H[x%m]=p;
}

int src(long x)
{
	hash *p;
	p=H[x%m];
	int ok=0;
	while(p!=NULL)
	{
		if(p->nod==x)
		{
			ok=1;
			break;
		}
		p=p->link;
	}
	return ok;
}

int main()
{
	freopen("secv5.in","r",stdin);
	freopen("secv5.out","w",stdout);

	scanf("%ld%ld%ld",&n,&a,&b);
	d[0]=0;
	m=999983;
	for(i=1;i<=m;i++) H[i]=NULL;
	for(i=1;i<=n;i++)
	{
		fscanf(stdin,"%ld",&v[i]);
		if(src(v[i])==0)
		{
			d[i]=d[i-1]+1;
			add(v[i]);
		}
		else d[i]=d[i-1];
	}
	for(i=1;i<=m;i++) H[i]=NULL;
	e[n+1]=0;
	for(i=n;i>0;i--)
		if(src(v[i])==0)
		{
			e[i]=e[i+1]+1;
			add(v[i]);
		}
		else e[i]=e[i+1];

	sol=0;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		{
			x=d[j]-d[i-1];
			if(x<e[i]-e[j+1]) x=e[i]-e[j+1];
			if(a<=x&&x<=b) sol++;
		}

	printf("%ld\n",sol);
	return 0;
}