Cod sursa(job #117384)

Utilizator alexeiIacob Radu alexei Data 21 decembrie 2007 13:08:54
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
int n,k,a[500001],co[500001],min,minmax;

int cauta(int p,int u,int x)
{
	int m;
	while(p<u){
		m=(p+u)/2;
		if(x<=a[co[m]])
			u=m;
		else
			p=m+1;
	}
	if(a[co[p]]<x)
		return p+1;
	return p;
}

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int min=30001,max,p=0,u=0,aa,bb;
	scanf("%d%d%d",&n,&k,&a[1]);
	co[u++]=1;
	for(int i=2; i<=k; i++){
		scanf("%d",&a[i]);
		u=cauta(p,u-1,a[i]);
		co[u++]=i;
		if(a[co[p]]<min)
			min=a[co[p]];
	}
	max=min;
	aa=1;bb=k;
	for(int i=k+1; i<=n; i++)
	{
		scanf("%d",&a[i]);
		if(co[p]+k<=i)
			++p;
		u=cauta(p,u-1,a[i]);
		co[u++]=i;
		min=a[co[p]];
		if(min>max){
			max=min;
			aa=i-k+1;
			bb=i;
		}
	}
	printf("%d %d %d\n",aa,bb,max);
	return 0;
}