Cod sursa(job #226159)

Utilizator ilincaSorescu Ilinca ilinca Data 1 decembrie 2008 05:24:32
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>

#define maxn 5000005

struct nimic
{
	int v, p;
};

int n, k, f, l;
nimic q [maxn];

void rez ()
{
	int i, x, w, max, fmax, lmax;
	scanf ("%d%d", &n, &k);
	for (i=1; i<=k; ++i)
	{
		scanf ("%d", &x);
		while (l > 0 && q [l].v > x) --l;
		q [++l].p=i;
		q [l].v=x;
	}
	f=fmax=1;
	lmax=l;
	max=q [1].v;
	for (i=k+1; i<=n; ++i)
	{
		scanf ("%d", &x);
		w=i-k;
		while (f <= l && q [f].p <= w) ++f;
		while (f <= l && q [l].v > x) --l;
		q [++l].p=i;
		q [l].v=x;
		if (q [f].v > max)
		{
			max=q [f].v;
			fmax=i-k+1;
			lmax=i;
		}
	}
	printf ("%d %d %d", fmax, lmax, max);
}

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