Cod sursa(job #249331)

Utilizator victorsbVictor Rusu victorsb Data 28 ianuarie 2009 00:38:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

#define Nmax 500015

int N, K;
int best_st, best_dr, best;
int sir[Nmax];
int D[Nmax];
char s[Nmax * 8], *buf;

int get()
{
	int ret = 0, sgn = 1;
	while (*buf == ' ') ++buf;
	if (*buf == '-') sgn = -1, ++buf;
	while ('0' <= *buf && *buf <= '9')
	{
		ret = ret * 10 + *buf - '0';
		++buf;
	}

	return ret * sgn;
}

void citire()
{
	scanf("%d%d\n", &N, &K);
	fgets(s, Nmax * 8, stdin);
	buf = s;
	for (int i = 1; i <= N; ++i)
		sir[i] = get();
}

void solve()
{
	int st = 1, dr = 0;

	best = -30001;
	for (int i = 1; i <= N; ++i)
	{
		while (st <= dr && sir[D[dr]] > sir[i]) --dr;
		D[++dr] = i;
		while (st <= dr && D[st] <= i - K) ++st;

		if (i >= K && best < sir[D[st]])
		{
			best = sir[D[st]];
			best_st = i - K + 1;
			best_dr = i;
		}
	}

	printf("%d %d %d\n", best_st, best_dr, best);
}

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

	citire();
	solve();

	return 0;
}