Cod sursa(job #120377)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 ianuarie 2008 12:01:23
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#define N 500001
int a[N],n,k,coada[N];
char s[N*7];
int caut(int st,int dr,int poz){
	int p=st,u=dr,m;
	while(p<u){
		m=(p+u)>>1;
		if(a[poz]<=a[coada[m]])
			u=m;
		else
			p=m+1;
	}
	if(a[coada[p]]<a[poz])
		return p+1;
	return p;
}
int main(){
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	gets(s);
	int semn=1,i=1,p,u,max,aa,bb;
	for(char*p=s;*p;++p)
		if(*p=='-')
			semn=-1;
		else
			if(*p==' '){
				semn=1;
				++i;
			}
			else
				a[i]=a[i]*10+semn*(*p-'0');
	/*
	for(i=1;i<=n;++i)
		printf("%d ",a[i]);
	printf("\n");
	*/
	p=u=0;
	coada[u]=1;
	for(i=2;i<=k;++i){
		u=caut(p,u,i);
		coada[u]=i;
	}
	max=a[coada[p]];
	aa=1;
	bb=k;
	for(i=k+1;i<=n;++i){
		u=caut(p,u,i);
		coada[u]=i;
		if(i-coada[p]>=k)
			++p;
		if(a[coada[p]]>max){
			aa=i-k+1;
			bb=i;
			max=a[coada[p]];
		}
	}
	printf("%d %d %d\n",aa,bb,max);
	return 0;
}