Cod sursa(job #132525)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 5 februarie 2008 23:58:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
//Problema 014.Secventa (Infoarena). Varianta cu heap.
//Complexitate O(N*logN)
#include <stdio.h>
#include <string.h>
int n, k, h[500000], p[500000], poz[500000], d, v[500000], nr;

void swap(int x, int y)
{
   int z;
   z = h[x]; h[x] = h[y]; h[y] = z;
   z = p[x]; p[x] = p[y]; p[y] = z;
   z = poz[p[x]]; poz[p[x]] = poz[p[y]]; poz[p[y]] = z;
}

void urc(int k)
{
   if (h[k] < h[(k-1)/2])
   {
      swap(k,(k-1)/2);
      urc((k-1)/2);
   }
}

void cobor(int k)
{
   int min, st, dr;
   st = 2 * k + 1;
   dr = 2 * k + 2;

   if (st < d && h[st] < h[k]) min = st;
   else min = k;

   if (dr < d && h[dr] < h[min]) min = dr;

   if (min != k)
   {
      swap(k,min);
      cobor(min);
   }
}

void adaug(int k)
{
   h[d] = k;
   urc(d);
   d++;
}

void sterg(int k)
{
   swap(k, d-1);
   d--;
   cobor(k);
}

void citire()
{
  freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);

  scanf("%ld %ld",&n,&k);
  long semn=0, aux, i;
  char sir[2000024];
  fgetc(stdin);
  fgets(sir, 2000024,stdin);
  aux=strlen(sir);
  nr=1;
  for (i=0; i<aux; i++)
    {
      if (sir[i]=='-') semn=1;
      if (sir[i]>='0' && sir[i]<='9')
	{	
	  v[nr]=v[nr]*10+sir[i]-'0';
	}
      if (sir[i]==' ' && semn)	v[nr]*=-1, semn=0;
      if (sir[i]==' ') nr++;
    }
}

int main()
{
   citire();
   int i, min = -32000, pi, pf;
   for (i = 1; i < k; i++) {p[d] = i; poz[i] = d; adaug(v[i]);}

   for (i = k; i <= n; i++)
   {
      p[d] = i; poz[i] = d;
      adaug(v[i]);
      if (min < h[0])
      {
	 min = h[0];
	 pi = i - k + 1;
	 pf = i;
      }
      sterg(poz[i-k+1]);
   }

   printf("%d %d %d\n",pi,pf,min);
   return 0;
}