Cod sursa(job #208593)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 17 septembrie 2008 11:11:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#define N 500010
int v[N],n,t,t2,h[N];
inline void swap(int &x,int &y){
	int z=x;x=y;y=z;
}
void sift(int h[],int k,int n){
	int son=0;
	do{
		if(2*k<=n) son=2*k;
		if(2*k+1<=n && v[h[2*k+1]]<v[h[son]]) son=2*k+1;
		if(v[h[son]]>=v[h[k]])
			son=0;
		else {
			swap(h[k],h[son]);
			k=son;
		}
	}
	while(son);
}
void percolate(int h[],int k,int n){
	while(k>1 && v[h[k]]<v[h[k/2]]){
		swap(h[k],h[k/2]);
		k/=2;
	}
}
void add(int h[],int key,int &n){
	h[++n]=key;
	percolate(h,n,n);
}
void cut(int h[],int k,int &n){
	h[k]=h[n];
	n--;
	if(k>1 && v[h[k/2]]>v[h[k]])
		percolate(h,k,n);
	else 
		sift(h,k,n);
}
void build_heap(int h[],int n){
	for(int i=n/2;i>0;i--)
		sift(h,i,n);
}
int main(){
	int i,min,x=0,semn=1;
	char s[7*N];
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&t);
	fgets(s,7*N,stdin);
	for(i=0;s[i]!='\0' && s[i]!='\n';i++){
		if(s[i]=='-') semn=-1;
		else if(s[i]>='0' && s[i]<='9')
			x=x*10+s[i]-'0';
		else{
			v[++v[0]]=x*semn;
			x=0;
			semn=1;
		}
	}
	v[++v[0]]=x*semn;
	for(i=1;i<=t;i++)
		h[i]=i;
	build_heap(h,t);min=v[h[1]];x=t;t2=t;
	for(i=t+1;i<=n;i++){
		while (i-t>=h[1]) 
			cut(h,1,t2);
		add(h,i,t2);
		if(v[h[1]]>min){
			min=v[h[1]];x=i;
		}
	}
	printf("%d %d %d",x-t+1,x,min);
	return 0;
}