Cod sursa(job #428050)

Utilizator laurenttlaurentiu pavel laurentt Data 28 martie 2010 19:03:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>

#define maxn 500001
#define minim -30000

int maxim,c,n,k,a[maxn],deque[maxn];

void cit()
{
	scanf("%d %d",&n,&k);
	int i;
	for(i=1; i<=n; i++)
		scanf("%d",&a[i]);
}

void rez()
{
	int inc,sf;
	inc=sf=0;
	deque[0]=1;
	int i;
	
	for(i=2; i<=k; i++)
	{
		while(a[i]<a[ deque[sf] ] && inc<=sf )
			sf--;
		if(inc==sf && a[i]<a[deque[inc]])
			deque[inc]=i;
		else
		
			deque[++sf]=i;
	}
	maxim=a[deque[inc] ];
	c=deque[inc];
	for(i=k+1; i<=n; i++)
	{
		if(deque[inc]<=i-k)
			inc++;
		
		while(a[deque[sf]]>a[i] && inc<=sf)
			sf--;
		
		if(inc==sf && a[i]<a[deque[inc]])
			deque[inc]=i;
		else
			deque[++sf]=i;
		
		if(maxim<a[deque[inc]])
		{
			maxim=a[deque[inc]];
			c=deque[inc];
		}
	}
}

void afis()
{
	printf("%d %d %d",c,c+k-1,maxim);
		
}

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