Cod sursa(job #858044)

Utilizator Marius96Marius Gavrilescu Marius96 Data 18 ianuarie 2013 14:47:52
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda ichb-locala-2013-10 Marime 1.02 kb
//brut cu normalizare

#include<cstdio>
#include<cstring>

#include<algorithm>
using std::sort;

int v[1050000];
int c[1050000];

struct str
{
	int n,i,nn;
}t[1050000];

bool compn (str a, str b)
{
	return a.n<b.n;
}

bool compi (str a, str b)
{
	return a.i<b.i;
}

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

	int a,b,n;
	scanf ("%d%d%d\n",&n,&a,&b);

	char s[100];
	for(int i=0;i<n;i++){
		gets (s);
		t[i].n=atoi (s);
		t[i].i=i;
	}

	sort (t,t+n,compn);
	int temp=-1;
	for(int i=0;i<n;i++){
		if(i==0||t[i].n>t[i-1].n)
			temp++;
		t[i].nn=temp;
	}
	sort (t,t+n,compi);
	for(int i=0;i<n;i++)
		v[i]=t[i].nn;

	int ret=0;

	for(int l=a;l<=n;l++){
		memset (c,0,sizeof c);

		int cnt=0;
		for(int i=0;i<l;i++){
			c[v[i]]++;
			if(c[v[i]]==1)
				cnt++;
		}

		if(cnt>=a&&cnt<=b)
			ret++;

		for(int i=l;i<n;i++){
			c[v[i]]++;
			if(c[v[i]]==1)
				cnt++;

			c[v[i-l]]--;
			if(c[v[i-l]]==0)
				cnt--;

			if(cnt>=a&&cnt<=b)
				ret++;
		}
	}

	printf ("%d",ret);
	return 0;
}