Cod sursa(job #9632)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 ianuarie 2007 16:28:35
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Unirea 2007, clasele 11-12 Marime 1.17 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 1048576

int a[maxn],p[maxn],c[maxn],b[maxn];
int n,x,y,diff,sol;

int cmp(int x,int y)
{
    return (a[x]<a[y]);
}

int search(int x)
{
    int front=0,middle,back=n-1,aux;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
          if (a[p[middle]]>=x)
          {
              aux=middle;
              back=middle-1;
          }
          else front=middle+1;
    }
    
    return aux;
}

int main()
{
    freopen("secv5.in","r",stdin);
    freopen("secv5.out","w",stdout);
    
    scanf("%d %d %d",&n,&x,&y);
    
    int i,j;
    
    for (i=0;i<n;i++) 
    {
        scanf("%d",&a[i]);
        p[i]=i;
    }
    
	sort(p,p+n,cmp);

	for (i=0;i<n;i++) b[i]=search(a[i]);

	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++) c[j]=0;
		diff=0;
        
		for (j=i;j<n;j++)
        {
          if (c[b[j]]==0) 
          {
               c[b[j]]++;
               diff++;
          }
          if ((diff>=x) && (diff<=y)) sol++;
          if (diff>y) break;
        }
    }
    
    printf("%d\n",sol);
    
    return 0;
}