Cod sursa(job #203979)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 21 august 2008 10:30:38
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#define N 500001
int n,k,v[N],c[N],p=1,u;
int caut(int x){
	int st=p,dr=c[0],m;
	//if(v[c[dr]]<x) return dr+1;
	//else if(v[c[dr]]==x) return dr;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[c[m]]>=x) dr=m;
		else st=m+1;
	}
	if(v[c[st]]<x)
		++st;
	return st;
}
void citeste(){
	int i,semn=1,nr=0;
	char s[7*N];
	fgets(s,7*N,stdin);
	for(i=0;s[i]!='\n' && s[i]!='\0';i++)
		if(s[i]=='-') semn=-1;
		else if(s[i]>='0' && s[i]<='9')
			nr=nr*10+semn*(s[i]-'0');
		else { 
			v[++v[0]]=nr;
			semn=1;
			nr=0;
		}
	v[++v[0]]=nr;
}
int main(){
	int max,x=1,y,z,i;
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	citeste();
	c[0]=c[1]=1;
	for(i=2;i<=k;i++){
		z=caut(v[i]);
		c[z]=i;
		c[0]=z;
	}
	max=v[c[1]];y=k;
	for(i=k+1;i<=n;i++){
		if(i-k>=c[p]) p++;
		z=caut(v[i]);
		c[z]=i;c[0]=z;
		if(v[c[p]]>max) max=v[c[p]],x=i-k+1,y=i;
	}
	printf("%d %d %d\n",x,y,max);
	return 0;
}