Cod sursa(job #131836)

Utilizator swift90Ionut Bogdanescu swift90 Data 4 februarie 2008 15:41:31
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
struct cod{
	int x,t;
};
cod coada[500100];
int main(){
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int n,k,i,p,u,mij,timp,inc,sf,max=-50000,aux,tfin;
	scanf("%d%d",&n,&k);
	scanf("%d",&coada[0].x);
	coada[0].t=0;
	max=coada[0].x;
	inc=0;
	sf=0;
	timp=0;
	for(i=1;i<k;++i){
		scanf("%d",&aux);
		p=inc;
		u=sf;
		while(p!=u){
			mij=(p+u)>>1;
			if(coada[mij].x<aux)
				p=mij+1;
			else
				u=mij;
		}
		if(coada[p].x<aux)
			++p;
		++timp;
		coada[p].x=aux;
		coada[p].t=timp;
		sf=p;
		if(coada[sf].x<max)
			max=coada[sf].x;
	}
	tfin=0;
	for(;i<n;++i){
		if(coada[inc].t+k<=i)
			++inc;
		scanf("%d",&aux);
		p=inc;
		u=sf;
		while(p!=u){
			mij=(p+u)>>1;
			if(coada[mij].x<aux)
				p=mij+1;
			else
				u=mij;
		}
		if(coada[p].x<aux)
			++p;
		++timp;
		coada[p].x=aux;
		coada[p].t=timp;
		sf=p;
		if(coada[inc].x>max){
			max=coada[inc].x;
			if(tfin+k>=i)
				++tfin;
			else
				tfin=i-k+1;
		}
	}
	printf("%d %d %d\n",tfin+1,tfin+k,max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}