Cod sursa(job #126912)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 ianuarie 2008 23:07:15
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
//secventa implementata cu deque
#include<stdio.h>
FILE*fin=fopen("secventa.in","r");
FILE*fout=fopen("secventa.out","w");
int main()
{
  int i,j,n,k,max,s,st,dr,v[500001],dec[500001],ind[500001];
  fscanf(fin,"%d%d",&n,&k);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&v[i]);
  fclose(fin);
  st=1;dr=1;
  dec[1]=v[1];ind[1]=1;s=k;
  j=1;
  for(i=2;i<=k;i++)
  {
    while(j>=st&&dec[j]>v[i]) j--;
    j++;dr=j;
    dec[dr]=v[i];
    ind[dr]=i;
  }
  max=dec[1];
  for(i=k+1;i<=n;i++)
  {
    if(ind[st]<i-k+1) st++;
    while(j>=st&&dec[j]>v[i]) j--;
    j++;dr=j;
    dec[dr]=v[i];
    ind[dr]=i;
    if(max<dec[st]){max=dec[st];s=i;}
  }
  fprintf(fout,"%d%c%d%c%d",s-k+1,' ',s,' ',max);
  fclose(fout);
  return 0;
}