Cod sursa(job #132524)

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

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);
}

int main()
{
   freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);

   int i, pi, pf, min = -32000;

   scanf("%d %d",&n,&k);
   for (i = 1; i <= n; i++) scanf("%d",v+i);

   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;
}