Cod sursa(job #97768)

Utilizator flionIonescu Ionut Florin flion Data 8 noiembrie 2007 18:04:28
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#define nmax 500005

int N, K, i, A[nmax], bottom, top, ult, V[nmax], P[nmax], max, aaa, bbb;

int main(void)
{
	max = -2000000000;

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

	scanf("%d %d", &N, &K);

	for (i = 1; i <= N; i++)
		scanf("%d", &A[i]);

	for (i = 1, bottom = 0, top = -1, ult = 0; i <= N - K + 1; i++)
	{
		while (ult < i + K - 1 && ult < N)
		{
			ult++;

			while (top >= bottom && V[top] >= A[ult])
				top--;

			top++;

			V[top] = A[ult];
			P[top] = ult;
		}

		while (P[bottom] < i)
			bottom++;

		if (V[bottom] > max)
		{
			max = V[bottom];
			aaa = i;
			bbb = i+K-1;

		}

	}

	printf("%d %d %d\n", aaa, bbb, max);

	return 0;
}