Cod sursa(job #11423)

Utilizator devilkindSavin Tiberiu devilkind Data 31 ianuarie 2007 17:55:41
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <string.h>
#include <map>
#define NMAX (1 << 20)+1
using namespace std;

FILE *f = fopen("secv5.in","rt"), *g = fopen("secv5.out","wt");

map<long int,long int> hash;

long int a[NMAX],n,i,j,k,v[NMAX],min1,max1;
long long L[NMAX];

void citire()
{
long int nr=0;
fscanf(f,"%ld %ld %ld",&n,&min1,&max1);
for (i=1;i<=n;i++)
    {fscanf(f,"%ld",&k);
    if (hash[k]) a[i]=hash[k];
       else {a[i]=++nr;
            hash[k]=nr;
            }
    } 
}

long long calcul(long int x)
{
long int start=0,final=0,nr=1;
for (i=1;i<=n;i++)
    {v[i]=0;L[i]=0;}
while (final<=n)
      {
      final++;
      v[a[final]]++;
      if (v[a[final]]==1) nr++;
      while (nr>x) {start++;
                   v[a[start-1]]--;
                   if (v[a[start-1]]==0) nr--;
                   }
      L[final]=start;
      if (L[final]==0) L[final]=final;
      }
long long sol;
for (i=1;i<=n;i++)
    sol=sol + (long long) (i - L[i]+1);
return sol;
}

int main()
{
citire();
long long s1,s2;
memset(L,0,sizeof(long int));
s1=calcul(min1);
s2=calcul(max1);
fprintf(g,"%lld",s2-s1);    
fclose(f);
fclose(g);
return 0;
}