Cod sursa(job #9514)

Utilizator blasterzMircea Dima blasterz Data 27 ianuarie 2007 15:59:28
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Unirea 2007, clasele 11-12 Marime 0.99 kb
#include <cstdio>
#define maxn 1<<20

int x[maxn], a[maxn], b[maxn], n, L, U;
int s[maxn];
void citire()
{
  freopen("secv5.in", "r", stdin);
 scanf("%d %d %d\n", &n, &L, &U);
 int i;
 for(i=1;i<=n;i++) scanf("%d\n", x+i);
}

void calcul()
{
  int i, j;
  a[1]=1;
  for(i=2;i<=n;i++)
    if(x[i]==x[i-1]) a[i]=a[i-1]+1;
    else a[i]=1;

  for(i=n-1;i>=1;i--)
    if(x[i]==x[i+1])
      a[i]=a[i+1];

  int T=1;
  b[T]=a[1];
  for(i=2;i<=n;i++)
    {
      if(a[i]==a[i-1] && (b[T]!=a[i] || x[i]!=x[i-1])) b[++T]=a[i];
      else if(a[i]!=a[i-1])b[++T]=a[i];
    } 
  // for(i=1;i<=T;i++) printf("%d ", b[i]);
  //printf("\n");

  s[1]=b[1];
  for(i=2;i<=T;i++) s[i]=s[i-1]+b[i];
  long long sum=0;

  for(i=L;i<=T;i++)
    {
      int p, q;
      p=i-L+1;
      q=i-U+1;
      if(q<=0) q=1;



      //  printf("%d %d %d %d %d\n", s[p], s[q-1], p, q,q);
      sum+=(s[p]-s[q-1])*b[i];
    }
  freopen("secv5.out", "w", stdout);
  printf("%lld\n", sum);



}

int main()
{
  citire();
  calcul();
  return 0;
}