Cod sursa(job #123931)

Utilizator savimSerban Andrei Stan savim Data 17 ianuarie 2008 19:04:08
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#define l 500001
int n,k,i,j,t,p1,p2,max;
int a[l],coada[l],poz[l];
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",&a[i]);
    
	coada[0]=-32000;poz[1]=1;
    coada[1]=a[1];t=1;
	for (i=2; i<=k; i++)
    {
        t++;
        coada[t]=a[i];
        poz[t]=i;
        while (coada[t]<coada[t-1])    
        {
              coada[t-1]=coada[t];poz[t-1]=poz[t];
              coada[t]=0;poz[t]=0;
              t--;
        }
    }
    max=coada[1];
	p1=1;p2=k;
	int linf=1;
	for (i=k+1; i<=n; i++)
	{
		t++;
        coada[t]=a[i];
        poz[t]=i;
		if (poz[linf]<i-k+1) linf++;
		while (coada[t]<coada[t-1] || poz[t-1]<i-k+1 && t>1)
		{
			  coada[t-1]=coada[t];poz[t-1]=poz[t];
			  coada[t]=0;poz[t]=0;
			  t--;
		}
		if (t<linf) linf=t;
		if (coada[linf]>max)
		{
		   max=coada[linf];
		   p1=i-k+1;
           p2=i;                 
        }
    }
	printf("%d %d %d\n",p1,p2,max);
        
    
    
    
    return 0;    
}