Cod sursa(job #196360)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 25 iunie 2008 21:27:12
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
FILE *f,*g;
int a[500001],q[500001],baza;
long i,n,k,poz[500001],inc,sf,pi,pf;
int main()
{ f=fopen("secventa.in","r"); g=fopen("secventa.out","w");
  fscanf(f,"%ld%ld",&n,&k);
  for(i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
  q[1]=a[1]; inc=sf=1; poz[1]=1;
  for(i=2;i<k;i++)
   { while(a[i]<=q[sf]&&sf>0) sf--; 
     q[++sf]=a[i];
     poz[sf]=i;
   }
  for(i=k;i<=n;i++)
   { while(i-poz[inc]>=k) ++inc;
     if(a[i]<q[inc]&&a[i]>baza) { baza=a[i]; pi=i-k+1; pf=i; }
     if(q[inc]<=a[i]&&q[inc]>baza) { baza=q[inc]; pi=i-k+1; pf=i; }
     while(a[i]<=q[sf]&&sf>0) --sf; q[++sf]=a[i]; poz[sf]=i;
     if(inc>sf) inc=sf; 
   }
  fprintf(g,"%ld %ld %d",pi,pf,baza);
  fclose(g);
  return 0;
}