Cod sursa(job #797756)

Utilizator Athena99Anghel Anca Athena99 Data 14 octombrie 2012 19:49:48
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>

const int d=500001;
int v[d],deq[d];

int main()
{
    int n=0,k=0,d1=1,d2=1,i=0,b=-d,s=1,f=0;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    scanf("%d%d",&n,&k);
    f=k;
    deq[1]=1;
    for (i=1; i<n+1; ++i)
        scanf("%d",&v[i]);

    for (i=2; i<k; i++)
    {
		while (v[deq[d1]]>=v[i] && d1>0)
			--d1;
		++d1;
		deq[d1]=i;
	}

	for(i=k; i<n+1; i++)
	{
		while (v[deq[d1]]>=v[i] && d1>=d2)
			--d1;
        ++d1;
		deq[d1]=i;
		if (v[deq[d2]]>b)
		{
			b=v[deq[d2]];
			s=i-k+1;
			f=i;
		}
		if (deq[d2]<i-k+2)
			d2++;
	}

    printf("%d %d %d\n",s,f,b);

	return 0;
}