Cod sursa(job #35937)

Utilizator robbyRobertino robert robby Data 22 martie 2007 18:19:52
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#define nmax 500001
int a[nmax],b[nmax],c[nmax],s[nmax],d[nmax];
int st, fn, 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;
  b[0]=a[0]=-30002;
  nr=0;
  for (i=1;i<=n+1;i++)
	{
	  if (i != n+1)
		fscanf(f,"%d",&a[i]);
	  while (b[nr]>=a[i])
		{
		  d[c[nr]]=i;
		  nr--;
		}
	  b[++nr]=a[i];
	  c[nr]=i;
	  s[i]=c[nr-1];
	}

  bz = -30001;

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

  fcloseall();
  return 0;
}