Cod sursa(job #237540)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 29 decembrie 2008 23:16:19
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
# include <stdio.h>
# define nmax 500001
long N,K,C[nmax];
int a[nmax],semn;
char s[nmax*10];

int main(){
  long i,st,dr,max=-30001,x=0,y=0,j=0;
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);
  scanf("%ld %ld\n",&N,&K);
  gets(s);   
  for(i=1;i<=N;i++){   
      semn=1;   
      while((s[j] != '-') && !((s[j] >= '0') && (s[j] <= '9'))) j++;   
      if(s[j]=='-') semn=-1,j++;   
      while((s[j] >= '0') && (s[j] <= '9')) a[i]=a[i]*10+(s[j]-'0'),j++;   
      a[i] *= semn;   
   }   
  st=1; dr=0;
  for (i=1;i<=N;i++){
    while (st<=dr && a[i]<=a[C[dr]]) dr--;
    C[++dr]=i;
    if (C[st]==i-K) st++;
    if (i>=K && a[C[st]]>max){
	  max=a[C[st]];
	  x=i-K+1; y=i;	}
  }
  printf("%ld %ld %ld",x,y,max);
  return 0;
}