Cod sursa(job #2526)

Utilizator alle_forever13Alexandra Retegan alle_forever13 Data 17 decembrie 2006 17:29:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <cmath>

using namespace std;

#define dim 500001

#define input  "secventa.in"
#define output "secventa.out"

int  a[dim], q[dim];

long n, k, i, st, dr, rez, poz;

int main()
{

	freopen(input, "r", stdin);
	freopen(output, "w", stdout);

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

	for(i=1; i<=n; i++)
		scanf("%ld", &a[i]);


	rez = -30001;	

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

			dr --;

		q[++dr] = i;
		


	}

	for ( i = k; i <= n; i ++)
	{
		while ( (st <= dr) && (a[i]<=a[q[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\n", poz-k+1,poz,rez);
	return 0;
}