Cod sursa(job #210392)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 27 septembrie 2008 16:22:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
#define N 500050
int n,v[N],coada[N],p,u,max=-30001,a,b,k;
void read(){
	int i;
	freopen("secventa.in","r",stdin);
	scanf("%d%d",&n,&k);
	for (i=1;i<=n;++i)
		scanf("%d",&v[i]);
}
void elimin(int i){
	while(p<u && coada[p]+k<=i)
		++p;
}
int caut(int x){
	int p2=p,u2=u,m;
	while(p2!=u2){
		m=(p2+u2)/2;
		if (x<=v[coada[m]])
			u2=m;
		else
			p2=m+1;
	}
	if (v[coada[p2]]<x)
		++p2;
	return p2;
}
void solve(){
	int i,q;
	coada[u++]=1;
	for(i=2;i<=k;++i){
		q=caut(v[i]);
		u=q;
		coada[u++]=i;
	}
	max=v[coada[0]];
	a=1;
	b=k;
	for(i=k+1;i<=n;++i){
		//elimin toate elem din coada care sunt prea indepartate de elm curent
		elimin(i);
		q=caut(v[i]);
		u=q;
		coada[u++]=i;
		if(v[coada[p]]>max){
			max=v[coada[p]];
			a=i-k+1;
			b=i;
		}
	}
}
void write(){
	freopen("secventa.out","w",stdout);
	printf("%d %d %d\n",a,b,max);
}
int main(){
	read();
	solve();
	write();
}