Cod sursa(job #203974)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 21 august 2008 10:14:13
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <stdio.h>
#define N 500001
int n,k,v[N],c[N],p=1,u;
int caut(int x){
	int st=p,dr=c[0],m;
	//if(v[c[dr]]<x) return dr+1;
	//else if(v[c[dr]]==x) return dr;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[c[m]]>=x) dr=m;
		else st=m+1;
	}
	if(v[c[st]]<x)
		++st;
	return st;
}
int main(){
	int max,x=1,y,z,i;
	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]);
	c[0]=c[1]=1;
	for(i=2;i<=k;i++){
		z=caut(v[i]);
		c[z]=i;
		c[0]=z;
	}
	max=c[1];y=k;
	for(i=k+1;i<=n;i++){
		while(i-k>=c[p]) p++;
		z=caut(v[i]);
		c[z]=i;c[0]=z;
		if(v[c[p]]>max) max=v[c[p]],x=i-k+1,y=i;
	}
	printf("%d %d %d\n",x,y,max);
	return 0;
}