Cod sursa(job #79592)

Utilizator gigi_becaliGigi Becali gigi_becali Data 23 august 2007 10:48:28
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<limits.h>
#include<string.h>

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

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

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


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

}