Cod sursa(job #150787)

Utilizator rethosPaicu Alexandru rethos Data 7 martie 2008 13:41:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <string.h>
#include <fstream.h>
#define NM 500001
#define INF 0x7fff
int a[NM],ind[NM],vf,baza;

void popvf()
{ vf--;
}

void popbaza()
{ baza++;
}

void push(int x,int k)
{ a[++vf]=x;
  ind[vf]=k;
}

int main()
{ long n,k;
  FILE *f=fopen("secventa.in","rt");
  fscanf(f,"%ld %ld",&n,&k);
  char c[NM*7];
  fgets(c,NM*7,f);
  fgets(c,NM*7,f);
  long l=strlen(c),p=-1;
  fclose(f);
  int max=-INF,kmax=1;
  int x,i,semn;
  vf=0;baza=1;
  for (i=1;i<k;i++)
	{ x=0;semn=1;p++;
	  while (p<l&&c[p]!=' ')
		{ if (c[p]=='-') semn=-1;
			else x=x*10+c[p]-'0';
		  p++;
		}
	  x=x*semn;
	  while (a[vf]>x&&vf>=baza) popvf();
	  push(x,i);
	}
  for (i=k;i<=n;i++)
	{ x=0;semn=1;p++;
	  while (p<l&&c[p]!=' ')
		{ if (c[p]=='-') semn=-1;
			else x=x*10+c[p]-'0';
		  p++;
		}
	  x=x*semn;
	  if (i-ind[baza]>=k) popbaza();
	  while (a[vf]>x&&vf>=baza) popvf();
	  push(x,i);
	  if (a[baza]>max)
		{ max=a[baza];
		  kmax=i-k+1;
		}
	}
  ofstream g("secventa.out");
  g<<kmax<<' '<<kmax+k-1<<' '<<max;
  g.close();
  return 0;
}