Cod sursa(job #9666)

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

using namespace std;

#define maxn 50010

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

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