Cod sursa(job #773775)

Utilizator predatorGigi Valoare predator Data 2 august 2012 16:01:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<stdio.h>
#define maxn 500001
short int D[maxn],A[maxn],min;
int i,n,k,back,front,inc,sf;
int main ()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	min=-30001;
	scanf("%d%d",&n,&k);
	front=1;
	back=0;
	for(i=1;i<=n;++i)
	{
		scanf("%d",&A[i]);
	}
	for(i=1;i<=n;++i)
	{
		while(front<=back&&A[i]<=A[D[back]]) --back;
		D[++back]=i;
		if(D[front]==i-k) ++front;
		if(A[D[front]]>min)
		{
				min=A[D[front]];
				inc=i-k+1;
				sf=i;
		}
	}
	printf("%d %d %d",inc,sf,min);
	return 0;
}