Cod sursa(job #258251)

Utilizator drag0s93Mandu Dragos drag0s93 Data 14 februarie 2009 22:01:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>

#define U 3500001

#define N 500001

char pr[U];

int max,a,b,v[N],n,k,d[N],p,u;

void cit()
{
	int nr=0,semn=1,x=0;
	scanf("%d%d\n",&n,&k);
	gets(pr);
	for(int i=0;pr[i];++i)
	{
		if(pr[i]==' ')
		{
			v[++nr]=semn*x;
			x=0;
			semn=1;
		}
		if(pr[i]=='-')
			semn=-1;
		if(pr[i]>='0' && pr[i]<='9')
			x=x*10+pr[i]-'0';
	}
	if(x)
		v[++nr]=semn*x;
	/*
	for(int i=1 ; i<=n ; ++i)
		printf("%d ",v[i]);
	*/
}

void stanga(int i)
{
	if(i-d[p]>=k)
		++p;
}

void dreapta(int i)
{
	while(p!=u && v[d[u-1]]>=v[i])
		--u;
	d[u++]=i;
}

void calc()
{
	for(int i=1;i<=k;++i)
		dreapta(i);
	max=v[d[p]];
	a=1;
	b=k;
	for(int i=k+1;i<=n;++i)
	{
		stanga(i);
		dreapta(i);
		if(v[d[p]]>max)
		{
			max=v[d[p]];
			a=i-k+1;
			b=i;
		}
	}
	printf("%d %d %d\n",a,b,max);
}

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