Cod sursa(job #515100)

Utilizator indestructiblecont de teste indestructible Data 20 decembrie 2010 13:24:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <stdio.h>
#define NMAX 500005
#define INF 2000000000
int n,k,A[NMAX],rez,st,dr,act,deq[NMAX],inc,sf;
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void baga(int poz)
{
	while (inc!=sf && A[deq[sf-1]]>=A[poz])
		sf--;
	deq[++sf]=poz;
}
void verifica(int poz)
{
	if (poz-deq[inc]>=k)
		inc++;
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&n,&k);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
	for (i=1; i<=n; i++)
	{
		baga(i);
		verifica(i);
		if (i>=k && A[deq[inc]]>rez)
			rez=A[deq[inc]],st=i-k+1,dr=i;
	}
	printf("%d %d %d\n",st,dr,rez);
	return 0;
}