Cod sursa(job #10927)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 29 ianuarie 2007 22:16:04
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define NMAX (1 << 20)
#define nd(a) (*(t_u *)(a))

typedef struct
{
	int x, y;
}t_u;

int cmp(const void *a, const void *b);
long long go(int x);
int N, A, B, V[NMAX], seen[NMAX], ult[NMAX];
t_u U[NMAX];

int main()
{
	int i, j, nr, k;
	long long rez = 0;
     
	freopen("secv5.in", "r", stdin);
     freopen("secv5.out", "w", stdout);

     scanf("%d%d%d", &N, &A, &B);
     for(i = 0; i < N; i++)
     {
     scanf("%d", V + i);
     /*U[i].x = V[i];
     U[i].y = i;*/
     }
	/*qsort(U, N, sizeof(t_u), cmp);
     for(i = 0, j = 0; i < N; i++)
     {
	     if(i && U[i].x != U[i - 1].x) j = i;
          V[U[i].y] = j;
     }*/

     for(i = 0; i < N; i++)
     for(j = 0; j <= i; j++)
     {
     	nr = 0;
	     for(k = j; k <= i; k++)
          if(!seen[V[k]]) seen[V[k]] = 1, nr++;
          if(nr >= A && nr <= B) rez++;
          for(k = j; k <= i; k++)
          seen[V[k]] = 0;
     }
     printf("%lld\n", rez);
     //printf("%lld\n", go(B) - go(A - 1));
	return 0;
}

long long go(int x)
{
	if(!x) return 0;

     int i, j, nr;
     long long rez = 0;

     memset(seen, 0, sizeof(seen));
     for(i = 0, j = 0, nr = 0; i < N; i++)
     {
     	if(seen[V[i]] == 1) rez += (i - j + 1), ult[V[i]] = i;
          else if(nr == x)
          	{
	               for(; j <= i && ult[V[j]] != j; j++);
                    seen[V[j]] = 0;
                    j++;
                    rez += (i - j + 1);
                    ult[V[i]] = i;
                    seen[V[i]] = 1;
               }
               else seen[V[i]] = 1, rez += (i - j + 1), ult[V[i]] = i, nr++;
     }
     return rez;
}

int cmp(const void *a, const void *b)
{
	return nd(a).x - nd(b).x;
}