Cod sursa(job #167384)

Utilizator pandaemonAndrei Popescu pandaemon Data 29 martie 2008 15:42:11
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NMAX 500001

long n,k,v[NMAX],m[NMAX],i=0; char s[NMAX*6],*p=s;

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

   scanf("%ld %ld",&n,&k); gets(s); gets(s);


   for(i=1;i<n;i++)
    {
      v[i]=atol(p); p=strchr(p,' '); p++;
    }

      v[n]=atol(p);


  long beg=1,end=0,max=-66666,poz=0;

  for(i=1;i<=n;i++)
    {
      if(beg<=end && m[beg]<=i-k) beg++;

      while(beg<=end && v[ m[end] ] > v[i] ) end--;

      m[++end]=i;

      if(i>=k && v[ m[beg] ] > max ) {poz=i; max = v[ m[beg] ];}

    }

    printf("%ld %ld %ld\n",poz-k+1,poz,max);

    return 0;

}