Cod sursa(job #138540)

Utilizator savimSerban Andrei Stan savim Data 18 februarie 2008 20:08:26
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define maxl 500010
int poz,max,x,y,r,n,k,i,p,q,t1,t2;
int a[maxl],c[maxl],t[maxl];
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]);
    
	max=-10000;
    p=1;q=1;
	c[p]=a[1];t[p]=1;
	for (i=2; i<=n; i++)
    {
        x=p-1;y=q+1;poz=p;
		if (a[i]<c[q])
		while (x+1<y)
        {
            r=(x+y)/2;
            if (c[r]>=a[i]) 
            {
                y=r;poz=r;
            }
            else x=r;
        }
		else poz=q+1;
		q=poz;
        c[q]=a[i];t[q]=i;
        
        x=p-1;y=q+1;poz=p;

		if (t[p]<i-k+1)
		while (x+1<y)
        {
            r=(x+y)/2;
			if (t[r]>=i-k+1)
            {
                y=r;poz=r;
            }
            else x=r;
        }
		p=poz;
              
		if (c[p]>max && i>=k)
        {
            max=c[p];
			t1=i-k+1;
            t2=i;
        }
    }
    
	printf("%d %d %d\n",t1,t2,max);
    return 0; 
}