Cod sursa(job #206896)

Utilizator tamicTamas Iulia tamic Data 10 septembrie 2008 16:24:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>
#define NMAX 500000

long v[NMAX],a[NMAX];
char s[NMAX*10];
long i,j,n,k,max,semn,msa,start;

void add(long x){
	long i;
	for(i=j; (i>=msa) && (a[i]>x);i--);
   j=i+1;
   a[j]=x;
}

int main(){
	freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);
   scanf("%ld%ld\n",&n,&k);
   gets(s);
   j=0;
   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')) v[i]=v[i]*10+(s[j]-'0'),j++;
      v[i] *= semn;
   }

   msa=1; j=0;
   for(i=1;i<=k;i++) add(v[i]);
   max=a[msa]; start=1;
   for(i=k+1;i<=n;i++){
   	if(v[i-k]==a[msa]) msa++;
      add(v[i]);
      if(a[msa]>max) max=a[msa],start=i-k+1;
   }

   printf("%ld %ld %ld\n",start,start+k-1,max);
   return 0;
}