Cod sursa(job #288886)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 26 martie 2009 10:27:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#define max 500032
#define mx 4194304
#define min -32768
#define IN "secventa.in"
#define OUT "secventa.out"

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

int n,k;
int maxim,prima,ultima,st,dr;
int v[max],deque[max];
char sir[mx];

int main()
{
 int i=0;
 int ind,x;
 int sw;

 fscanf(fin,"%d %d",&n,&k);
 fgets(sir,mx,fin); /// null
 fgets(sir,mx,fin);
  fclose(fin);

 ind=0;
 back:
 x=0;
 sw=1;
 for(;!(sir[ind]>='0' && sir[ind]<='9');ind++); /// determin daca are '-' in fata
 if(sir[ind-1]=='-')
  sw=-1;
 for(;sir[ind]>='0' && sir[ind]<='9';ind++)
  x=x*10+(sir[ind]-'0');
 v[++i]=sw*x;

 if(i!=n)
  goto back;

 for(i=1,maxim=min,st=1,dr=0;i<=n;i++)
 {
  while(st<=dr && v[i]<=v[deque[dr]])
   --dr;

  deque[++dr]=i;

  if(deque[st]==i-k)
   ++st;

  if(i>=k)
   if(v[deque[st]]>maxim)
   {
    maxim=v[deque[st]];
    prima=i-k+1;
    ultima=i;
   }
 }

 fprintf(fout,"%d %d %d",prima,ultima,maxim);
  fclose(fout);

 return 0;
}