Cod sursa(job #35945)

Utilizator diac_paulPaul Diac diac_paul Data 22 martie 2007 18:48:48
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#define nmax 500001
int a[nmax],c[nmax],s[nmax];//,d[nmax];
int st, bz;

FILE *f,*g;
int main()
{
  long n,k,i,j,nr;
  f=fopen("secventa.in","rt");
  g=fopen("secventa.out","wt");
  fscanf(f,"%ld %ld\n",&n,&k);
  a[n+1]=-30001;
  a[0]=-30002;
  nr=0;
  bz = -30001;

  for (i=1;i<=n+1;++i)
	{
	  if (i != n+1)
		fscanf(f,"%d",&a[i]);
	  while (a[c[nr]]>=a[i])
		{
//		  d[c[nr]]=i;
		  nr--;
		}
	  c[++nr]=i;
	  s[i]=c[nr-1];
	  if (i-s[i]+1 >= k && bz < a[s[i]])
	  {
		bz = a[s[i]];
		st = s[i];
	  }
	}


/*  for (i = 1; i <= n; ++i)
  {
	if (d[i] - s[i] - 1 >= k && a[i] > bz)
	{
		bz = a[i];
		st = s[i]+1;
	}
  }*/
  fprintf(g, "%d %d %d\n", st, st+k-1, bz);

  fcloseall();
  return 0;
}