Cod sursa(job #3862)

Utilizator MaGdUtZaVasile Maria-Magdalena MaGdUtZa Data 29 decembrie 2006 09:59:45
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>
#include<values.h>

#define dim 500002

#define infinit MAXLONG-1

long n,k,i,st,dr,rez,poz,a[dim],q[dim];

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);

	scanf("%ld%ld", &n, &k);

	for(i=1; i<=n; ++i)

		scanf("%ld", &a[i]);

	rez=-infinit;

	st=1;

	dr=0;

	for(i=1; i<k; ++i)
	{
		while(dr>=st && a[i]<=a[q[dr]])

			--dr;

		++dr;

		q[dr]=i;

	}
	for(i=k; i<=n; ++i)
	{
		while(st<=dr && a[i]<=a[q[dr]])

			--dr;

		++dr;

		q[dr]=i;

		while(st<=dr && q[st]<i-k+1)

			++st;

		if(a[q[st]]>rez)
		{
			rez=a[q[st]];
			poz=i;
		}
	}
	printf("%ld %ld %ld", poz-k+1, poz, rez);

	return 0;
}