Cod sursa(job #196349)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 25 iunie 2008 20:31:32
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
FILE *f,*g;
int a[500000],q[500000],baza;
long i,n,k,poz[500000],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; baza=a[1]; poz[1]=1;
  for(i=2;i<k;i++)
   { while(a[i]<=q[sf]&&sf>0) sf--; sf++;
     q[sf]=a[i];
     poz[sf]=i;
   }
  baza=q[1]; pi=1; pf=sf;
  for(i=k;i<=n;i++)
   { while(i-poz[inc]+1>k) inc++;
     if(a[i]<q[inc]&&a[i]>baza) { baza=a[i]; pi=poz[inc]; pf=i; }
     if(q[inc]<=a[i]&&q[inc]>baza) { baza=q[inc]; pi=poz[inc]; pf=i; }
     while(a[i]<=q[sf]&&sf>=inc) sf--; if(inc>sf) sf=inc-1; sf++;
     q[sf]=a[i];
     poz[sf]=i;
   }
  fprintf(g,"%ld %ld %d",pi,pf,baza);
  fclose(g);
  return 0;
}