Cod sursa(job #137056)

Utilizator ScrazyRobert Szasz Scrazy Data 16 februarie 2008 20:17:08
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
//O(n) deque
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define nmax 500004

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

char S[nmax<<3];

int main(void)
{
	max = -2000000000;

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

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

	gets(S);

	A[1] = atoi(strtok(S, " \n"));

	for (i = 2; i <= N; i++)
		A[i] = atoi(strtok(NULL, " \n"));

	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;
}