Cod sursa(job #110031)

Utilizator hadesgamesTache Alexandru hadesgames Data 25 noiembrie 2007 16:21:49
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
int d[500001],c[500001];
int cauta(int val,int p,int u)
/*{
	int m;
	while (p<u)
	{
		m=(p+u)/2;
		if (x<=c[m])
			u=m;
		else
			p=m+1;
	}
	if (c[p]>=x)
		return p;
	return p+1;
}*/
//int binary_search(int val)  
{  
    int i, step, N=u-p+1;  
    for (step = 1; step < N; step <<= 1);  
    for (i = 0; step; step >>= 1)
		if (i + step < N && c[i + step +p] <= val)  
            i += step;
	if (c[i+p]>=val)
		return i+p;
	return i+p+1;  
}  
int main()
{
	FILE *in,*out;
	int n,k,aux,a,b,p,u,min,i,t;
	in=fopen("secventa.in","r");
	out=fopen("secventa.out","w");
	fscanf(in,"%d%d",&n,&k);
	min=-31000;
	a=0;
	b=0;
	p=1;
	u=1;
	fscanf(in,"%d",&aux);
	c[1]=aux;
	d[1]=1;
	for (i=2;i<k;i++)
	{
		fscanf(in,"%d",&aux);
		t=cauta(aux,p,u);
		c[t]=aux;
		d[t]=i;
		u=t;
	}
	for (i=k;i<=n;i++)
	{
		fscanf(in,"%d",&aux);
		if (i-d[p]==k)
			p++;
		t=cauta(aux,p,u);
		c[t]=aux;
		d[t]=i;
		u=t;
		if (min<c[p])
		{
			min=c[p];
			a=i-k+1;
			b=i;
		}
		
	}
	fprintf(out,"%d %d %d\n",a,b,min);
	fclose(in);
	fclose(out);
}