Cod sursa(job #94802)

Utilizator slayer4uVictor Popescu slayer4u Data 25 octombrie 2007 20:13:27
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#include<string.h>
int i,n,dq[500001],k,kk,x[500001],inc,sf,msf,nr,minc,max=-2147000000,lg,minus;
char s[1000001];
int main()
{
	freopen ("secventa.in","rt",stdin);
	freopen ("secventa.out","wt",stdout);

	scanf("%ld %ld\n",&n,&k);
	fgets(s,1000001,stdin);
	lg=strlen(s);
	nr=0;
	kk=0;
	minus=1;
	for (i=0;i<=lg;i++)
	{
		if (s[i]>='0' && s[i]<='9')
			nr=nr*10+(s[i]-'0');
		else
			if (s[i]=='-')
				minus=-1;
		else
			x[++kk]=nr*minus,nr=0,minus=1;
	}
	/*
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);*/
	inc=1;sf=0;
	for (i=1;i<=n;i++)
	{
		while (sf>=inc && x[dq[sf]]>=x[i])
			sf--;
		dq[++sf]=i;

		if (i-dq[inc]>=k)
			inc++;
		if (x[dq[inc]]>max && i>=k)
		{
			max=x[dq[inc]];
			msf=i;
			minc=i-k+1;
		}
	}
	
	printf("%ld %ld %ld\n",minc,msf,max);
	return 0;
}