Cod sursa(job #132340)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 5 februarie 2008 17:33:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
FILE*fin=fopen("secventa.in","r");
FILE*fout=fopen("secventa.out","w");
char ss[4000000];
int i,j,n,k,max,s,st,dr,v[500001],dec[500001],ind[500001];
int main()
{

	fscanf(fin,"%d%d\n",&n,&k);

	fgets(ss,4000000,fin);
	fclose(fin);
	j=0;
	for(i=1;i<=n;i++)
	{
		v[i]=0;
		int min=0;
		while(ss[j]!=' '&&ss[j]!='\n')
		{
			if(ss[j]=='-') min=1;
			else v[i]=v[i]*10+ss[j]-'0';
			j++;
		}
		if(min) v[i]=-v[i];
		j++;
	}
  st=dr=1;
  dec[1]=v[1]; 
  ind[1]=1;s=k;
  j=1;
  for(i=2;i<=k;i++)
  {
    while(j>=st&&dec[j]>v[i]) j--;
    j++;dr=j;
    dec[dr]=v[i];
    ind[dr]=i;
  }
  max=dec[1];
  for(;i<=n;i++)
  {
    if(ind[st]<(i-k+1)) st++;
    while(j>=st&&dec[j]>v[i]) j--;
    j++;dr=j;
    dec[dr]=v[i]; 
    ind[dr]=i;
    if(max<dec[st])
    {
      max=dec[st]; 
      s=i;
    }
  }
  fprintf(fout,"%d%c%d%c%d",s-k+1,' ',s,' ',max);
  fclose(fout);return 0;}