Cod sursa(job #164635)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 24 martie 2008 16:50:16
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#define N 500000
#define INF 1000000
int v[N],q[N];
int n,k,st,dr,rez,poz;
void scan()
{
	freopen("secventa.in", "r",stdin);
	freopen("secventa.out", "w",stdout);
	scanf("%d%d", &n,&k);
	for(int i=1;i<=n;++i)
		scanf("%d", &v[i]);
}
void solve()
{
	rez=-INF;
	st=1; dr=0;
	for(int i=1;i<=k-1;++i)
	{
		while(dr>=st && v[i]<=v[q[dr]] )
			{dr-=1; }
		dr+=1;
		q[dr]=i;
	}
	for(int i=k;i<=n;++i)
	{
		while(st<=dr && v[i]<=v[q[dr]])
			{dr-=1; }
		dr+=1;
		q[dr]=i;
		while(st<=dr && q[st]<i-k+1)
			st+=1;
		if(v[q[st]]>rez)
		{
			rez=v[q[st]];
			poz=i;
		}
	}
}
void print()
{
	printf("%d %d %d\n",poz-k+1,poz,rez);	
}	
int main()
{
	scan();
	solve();
	print();
	return 0;
}