Cod sursa(job #48964)

Utilizator lucibitLucian Onea lucibit Data 5 aprilie 2007 10:56:47
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#define maxn 1048577 
long n,l,u,viz[maxn],a[maxn],a2[maxn],nr,NR;
void interc(long p, long q)
{long i,j,k,m;
 long a1[maxn];
 m=(p+q)/2;
 i=p; j=m+1;
 k=0;
 while (i<=m && j<=q)
		 if(a2[i]<a2[j]) a1[++k]=a2[i++];
		 else a1[++k]=a2[j++];
 while (i<=m) a1[++k]=a2[i++];
 while (j<=q) a1[++k]=a2[j++];
 for(i=p,k=1;i<=q;i++,k++) a2[i]=a1[k];


 }
void sort(long p, long q)
{if(p!=q) {sort(p,(p+q)/2); sort((p+q)/2+1,q);
				interc(p,q);
				}
}
long cb(long p , long q,long x)
{if(p==q) return q;
 else {if(x<=a2[(p+q)/2]) cb(p,(p+q)/2,x);
		 else cb((p+q)/2+1,q,x);}
 }
int main ()
{long i;
freopen ("secv5.in","r",stdin);
scanf("%ld %ld %ld\n",&n,&l,&u);
for(i=1;i<=n;i++) {scanf("%ld\n",&a[i]);a2[i]=a[i];}
sort(1,n);
nr=1;
i=2;
while(i<=n) {while (a2[i]==a2[nr] && i<=n) i++;
				  if(a2[nr]!=a2[i] && i<=n) a2[++nr]=a2[i];
				  }


long pi,pf,nrD,NR,c,j;
NR=0;
for(pi=1;pi<=n;pi++)
{for(j=1;j<=nr;j++) viz[j]=0;
 nrD=1;
  viz[cb(1,nr,a[pi])]++;
  pf=pi;
  while(nrD<l && pf<n) {pf++;
								c=cb(1,nr,a[pf]);
								 if(viz[c]==0)  nrD++;
								 viz[c]++;
								}
  while( nrD>=l && nrD<=u && pf<=n) { NR++;
								 pf++;
								 if(pf<=n)
								 {c=cb(1,nr,a[pf]);
								 if(viz[c]==0)  nrD++;
								 viz[c]++;}
								 }


 }

nrD=0;
freopen ("secv5.out","w",stdout);
printf("%ld\n",NR);
return 0;}