Cod sursa(job #226168)

Utilizator ilincaSorescu Ilinca ilinca Data 1 decembrie 2008 06:15:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#define maxn 500005
#define inf 30005

struct nimic
{
	int v, p;
};

int n, k, f, l, x [maxn];
char c [10*maxn];
nimic q [maxn];

void scan ()
{
	int i, s=1;
	scanf ("%d%d\n", &n, &k);
	gets (c);
	x [0]=1;
	for (i=0; c [i] != '\0' && c [i] != '\n'; ++i)
		if (c [i] == '-')
			s=-1;
		else
			if (c [i] >= '0' && c [i] <= '9')
				x [x [0]]=x [x [0]]*10+c [i]-'0';
			else
			{
				x [x [0]]*=s;
				s=1;
				++x [0];
			}
	x [x [0]]*=s;
}	

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

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