Cod sursa(job #380412)

Utilizator liv182copoiu liviu liv182 Data 6 ianuarie 2010 09:23:44
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
int dq[1<<19],v[1<<19],k,dr=1,st=0,max=0,stm,drm,n,i;
void stanga(int i)
{
    if(i-dq[st]==k)
        ++st;
}
void dreapta(int i)
{
    while(st<=dr&& v[dq[dr]]>=v[i])
        --dr;
    dq[++dr]=i;
}


int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for(i=1;i<k;++i)
		dreapta(i);
	for(i=k;i<=n;++i)
	{
		stanga(i);
		dreapta(i);
		if(v[dq[st]]>max) 
		{ 
			stm=i-k+1;
			drm=i;
			max=v[dq[st]];
		}
	}
	printf("%d %d %d",stm,drm,max);
	return 0;
}