Cod sursa(job #249322)

Utilizator victorsbVictor Rusu victorsb Data 28 ianuarie 2009 00:25:13
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>

#define Nmax 500015

int N, K;
int best_st, best_dr, best;
int sir[Nmax];
int D[Nmax];

void citire()
{
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &sir[i]);
}

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 (best < sir[D[st]])
		{
			best = sir[D[st]];
			best_st = D[st];
			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;
}