Cod sursa(job #131843)

Utilizator swift90Ionut Bogdanescu swift90 Data 4 februarie 2008 15:58:25
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
#include<string.h>
#define lim 3150000
struct cod{
	int x,t;
};
cod coada[500100];
char sir[lim];
int ax[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",&n,&k);
	inc=0;
	sf=0;
	timp=0;
	fgets(sir,lim,stdin);
	int l=strlen(sir),semn;
	p=0;
	for(i=0;i<=l;++i){
		if(sir[i]==' ' || sir[i]=='\n'){
			if(semn==1)
				ax[p]=aux;
			else
				ax[p]=-aux;
			semn=1;
			aux=0;
			++p;
		}
		if(sir[i]=='-')
			semn=-1;
		if('0'<=sir[i] && sir[i]<='9')
			aux=aux*10+(sir[i]-'0');
	}
	coada[0].x=ax[0];
	coada[0].t=0;
	max=coada[0].x;
	for(i=1;i<k;++i){
		p=inc;
		u=sf;
		while(p!=u){
			mij=(p+u)>>1;
			if(coada[mij].x<ax[i])
				p=mij+1;
			else
				u=mij;
		}
		if(coada[p].x<ax[i])
			++p;
		++timp;
		coada[p].x=ax[i];
		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;
		p=inc;
		u=sf;
		while(p!=u){
			mij=(p+u)>>1;
			if(coada[mij].x<ax[i])
				p=mij+1;
			else
				u=mij;
		}
		if(coada[p].x<ax[i])
			++p;
		++timp;
		coada[p].x=ax[i];
		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;
}