Cod sursa(job #321854)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 iunie 2009 16:51:56
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#define Nmax 500005
#define INF -32000

long a[Nmax],deq[Nmax],poz[Nmax];
long i,j,n,min=INF,k,z,nd,st,dr;

int main(){
	freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);
   scanf("%ld%ld",&n,&k);
   for(i=1;i<=n;++i) scanf("%ld",&a[i]);

   z=1;
   for(i=1;i<=n;++i){
   	if(a[i]>=deq[nd]) deq[++nd]=a[i],poz[nd]=i;
      else{
        while(a[i]<deq[nd] && nd>z) nd--;
        deq[++nd]=a[i];
        poz[nd]=i;
      }

      while(poz[z] < i-k+1) z++;
      if(deq[z]>min && i>=k){
      	min=deq[z];
         dr=i;
         st=dr-k+1;
      }
   }

   printf("%ld %ld %ld",st,dr,min);
   fclose(stdin); fclose(stdout);
   return 0;
}