Cod sursa(job #23296)

Utilizator pocaituDavid si Goliat pocaitu Data 28 februarie 2007 16:42:10
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream.h>
#include<stdio.h>
#define infi 32001
int long pos[500003],ind,sf,inc,d,max,i,n,k,j;
int st[500003],x;
int main()
{//char sir[5000];
 freopen("secventa.in","r",stdin);
 scanf("%ld%ld",&n,&k);
 scanf("%d",&st[1]);
 st[0]=-infi;
 inc=sf=1;
 pos[sf]=1;
 //fgets(sir,500000,stdin);
 //ind=0;

 for(i=2;i<=k;i++)
   {scanf("%d",&x);
	//for(x=0,++ind;sir[ind]>='0'&&sir[ind]<='9';ind++)
	//	x=x*10+sir[ind]-'0';

	for(;st[sf]>=x;sf--);
	st[++sf]=x;
	pos[sf]=i;
   }
 max=st[1];
 for(i=k+1;i<=n;i++)
  {scanf("%d",&x);
   //for(x=0,++ind;sir[ind]>='0'&&sir[ind]<='9';ind++)
   //		x=x*10+sir[ind]-'0';
	// inc++;
   for(;st[sf]>=x;sf--);
   //while(sf>=inc&&st[sf]>=x) sf--;
   st[++sf]=x;
   pos[sf]=i;
   if(pos[inc]<=i-k)
	 st[inc++]=-infi;

   if(st[inc]>max)
	 {max=st[inc];
	  d=i;
	  }
   }

 ofstream g("secventa.out");
 g<<d-k+1<<" "<<d<<" "<<max;
 g.close();
 return 0;
 }