Cod sursa(job #321900)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 iunie 2009 18:09:14
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string.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,semn,ls;

void pars(){
	char s[300];long z=0,nr=0;
   while ( !feof(stdin)){
      gets(s);  ls=strlen(s);
      for(i=0;i<ls;++i)
        if('0' <= s[i] && s[i]<='9'){if(nr==-1)nr=0; nr = nr*10+s[i]-'0';}
        else
        if(s[i]=='-') semn=-1;
        else
        if(s[i]==' ' && nr!=-1){
          a[++z]=nr*semn;
        	 nr=-1; semn=1;
        }
   }
   if(nr!=-1) a[++z]=nr;
}

int main(){
	freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);
   scanf("%ld%ld\n",&n,&k);
   pars();

   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=poz[z-1]+1;
      }
   }

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