Cod sursa(job #79370)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 22 august 2007 00:04:04
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<limits.h>
#include<string.h>
#define Dim 500000

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

#define cit(x)						\
{	char buf[500020];						\
	x = 0;						\
	while(buf[poz] < '0' || buf[poz] > '9')		\
		if(++poz == Dim)			\
			fread(buf,1,Dim,stdin), poz = 0;		\
	while(buf[poz] >= '0' && buf[poz] <= '9')	\
	{						\
		x = x*10 + buf[poz] - '0';		\
    		    if(++poz == Dim)			\
			fread(buf,1,Dim,stdin), poz = 0;		\
	}						\
}	

void read()
{
	int i;
    cit(n);
    cit(k);

	for(i = 1; i <= n; ++i)
       cit(a[i]);
}

int main()
{
  read();
  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<=nr; 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("%ld %ld %ld",poz-k+1, poz, rez);
  return 0;

}