Cod sursa(job #140393)

Utilizator za_wolfpalianos cristian za_wolf Data 21 februarie 2008 20:32:17
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define NMAX 500001
char s[NMAX*6];
int p,in,sf,x[NMAX],nr,i,j,semn,n,p1,p2,max,m,k,l,a,poz;
struct deque
{
	int V,I;
};
deque q[NMAX];
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&n,&k);
/*	gets(s);
	gets(s);
	poz=0;
	m=strlen(s)-1;
	n=0;
	while (poz<=m)
	{
		if (s[poz]=='-')
			semn=-1;
		else
		{
			semn=1;
			poz--;
		}
		nr=0;
		while (isdigit(s[++poz]))
			nr=nr*10+s[poz]-48;
		poz++;
		x[++n]=semn*nr;
	} */
	for (i=1;i<=n;i++)
		scanf("%d",&x[i]);
	max=31000;
	in=1;
	sf=1;
	q[1].I=1;
	q[1].V=x[1];
	i=2;
	for (i=2;i<=n;i++)
	{
	while (in<=sf&&q[in].I<=i-k)
			in++;
	while (sf>=in&&x[i]<=q[sf].V)
		sf--;

		q[++sf].V=x[i];
		q[sf].I=i;
		if (q[in].V>max&&i-k+1>=0)
		{
			max=q[in].V;
			p1=i-k+1;
			p2=i;
		}
	}

	printf("%d %d %d\n",p1,p2,max);

	return 0;
}