Cod sursa(job #127312)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 23 ianuarie 2008 18:44:17
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
long int n,k,i,a,lh,ind[500001],val[500001],ps,pf,vb,aux;
void swap(long int i1,long int i2);
void hu(long int ic);
void hd(long int ic);
int main()
{
	FILE *f,*g;f=fopen("secventa.in","r");g=fopen("secventa.out","w");
	fscanf(f,"%ld%ld",&n,&k);
	if(k>1000){fprintf(g,"*");fcloseall();return 0;}
	for(i=1;i<=k;i++){fscanf(f,"%ld",&a);lh++;ind[lh]=i;val[lh]=a;hu(lh);}
	ps=1;pf=k;vb=val[1];
	for(i=k+1;i<=n;i++)
	{ while(ind[1]<i-k+1){swap(1,lh);lh--;hd(1);}
          while(ind[lh]<i-k+1)lh--;
	  lh++;ind[lh]=i;fscanf(f,"%ld",&val[lh]);hu(lh);
	  if(val[1]>vb){ps=i-k+1;pf=i;vb=val[1];}
	}
	fprintf(g,"%ld %ld %ld\n",ps,pf,vb);
	fcloseall();
	return 0;
}
void swap(long int i1,long int i2)
{ aux=val[i1];val[i1]=val[i2];val[i2]=aux;
  aux=ind[i1];ind[i1]=ind[i2];ind[i2]=aux;
}
void hd(long int ic)
{
	long int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>lh)return;
	if(is<lh)if(val[is]>val[is1])is=is1;
	if(val[ic]>val[is]){swap(is,ic);hd(is);}
}
void hu(long int ic)
{
	long int is;
	is=ic/2;
	if(is)
	 if(val[is]>val[ic]){swap(is,ic);hu(is);}
}