Cod sursa(job #273982)

Utilizator DjSefuWrong name DjSefu Data 9 martie 2009 12:12:59
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<stdio.h>
#define MAXN 500005
FILE *f=fopen("secventa.in","r"),
     *g=fopen("secventa.out","w");
int deque[MAXN],a[MAXN],p,q,i,j,n,k,max,pf,qf;
int main()
{ fscanf(f,"%d %d",&n,&k);
  for(i=1;i<=n;++i) fscanf(f,"%d",&a[i]);
  p=1;
  q=0;
  max=-20000000;
  for(i=1;i<=n;++i){ while(p<=q&&a[i]<=a[deque[q]]) --q;
                     deque[++q]=i;
                     if(deque[p]==i-k) ++p;
                     if(i>=k) if(a[deque[p]]>max) max=a[deque[p]],pf=i-k+1,qf=i;
                   }
  fprintf(g,"%d %d %d\n",pf,qf,max);
  fclose(f);
  fclose(g);
  return 0;
}