Cod sursa(job #253113)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 5 februarie 2009 14:15:28
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#define N 501200
int n,v[N],coada[N],p,u,max=-30001,a,b,k;
void read(){
	int i,semn,x;
	char sir[N];
	freopen("secventa.in","r",stdin);
	scanf("%d%d\n",&n,&k);
	fgets(sir,N,stdin);
	for (i = 0, x = 0, n = 0, semn = 1; sir[i]; ++i)
	{
		if (sir[i] == ' ')
		{
			v[++n] = x * semn;
			x = 0;
			semn = 1;
		}
		else if (sir[i] == '-')
			semn = -1;
		else if (sir[i] >= '0' && sir[i] <= '9')
			x = x * 10 + (sir[i] - '0');
	}
	v[++n]=x*semn;
} 
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();
}