Cod sursa(job #79244)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 21 august 2007 14:04:17
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#include<limits.h>

long long n, k, i, st, dr, rez, poz, a[500001], q[500001], nr;

int main()
{
  freopen("secventa.in","r",stdin);
  freopen("secventa.out","w",stdout);
  scanf("%lld %lld",&n,&k);
  int ind, x;
  char sir[1024];
  fgets(sir, 1024, stdin), x = ind = 0;
  for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
    { x = x*10+(sir[ind]-'0'); a[++nr]=x;}

/*  scanf("%lld %lld",&n,&k);
  for (i=1; i<=n; i++)
    scanf ("%lld",&a[i]);*/
  rez=LONG_MIN;
  st=1, dr=0;
  for (i=1; i<=k-1; i++)
    {
      while(dr>=st && a[i]<=a[q[dr]]) dr--;
      dr++;
      q[dr]=i;
    }
  for (i=k; i<n; i++)
    {
      while (st<=dr && a[i]<=a[q[dr]]) dr--;
      dr++;
      q[dr]=i;
      while (st<=dr && q[st]<i-k+1) st++;
      if (a[q[st]]>rez)
	{
	  rez=a[q[st]];
	  poz=i;
	}
    }

  printf("%lld %lld %lld",poz-k+1, poz, rez);
  return 0;

}