Cod sursa(job #111883)

Utilizator hadesgamesTache Alexandru hadesgames Data 2 decembrie 2007 12:30:30
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <stdio.h>
#include <string.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,a,b,p,u,min,i,t,nr,nr2,poz;
	char s; 
	in=fopen("secventa.in","r");
	out=fopen("secventa.out","w");
	fscanf(in,"%d%d\n",&n,&k);
	min=-31000;
	a=0;
	b=0;
	p=1;
	u=0;
	/*fscanf(in,"%s",s);
	aux=strlen(s);
	aux2=0;
	for (i=0;i<aux;i++)
	{
		nr=0;
		nr2=1;
		if (s[i]=='-')
		{
			nr2=-1;
			i++;
		}
		while (s[i]>='0'&&s[i]<='9')
			nr=nr*10+s[i]-'0';
		nr*=nr2;
		aux2++;
		if (aux2==1)
		{
			u=1;
			c[1]=nr;
			d[1]=1;
		}
		if (aux2<k&&aux2!=1)
		{
			t=cauta(nr,p,u);
			c[t]=nr;
			d[t]=aux2;
			u=t;
		}
		if (aux2>=k)
		{
			if (i-d[p]==k)
				p++;
			t=cauta(nr,p,u);
			c[t]=nr;
			d[t]=aux2;
			u=t;
			if (min<c[p])
			{
				min=c[p];
				a=aux2-k+1;
				b=aux2;
			}
		}
		i++;
		
	}*/
//	c[1]=aux;
	//d[1]=1;
	poz=0;
	for (i=1;i<k;i++)
	{
		poz=0;
		nr=0;
		nr2=1;
		fscanf(in,"%c ",&s);
		if (s=='-')
		{
			nr2=-1;
			fscanf(in,"%c ",&s);
		}
		while (s>='0'&&s<='9')
		{
			nr=nr*10+s-'0';
			fscanf(in,"%c ",&s);
		}
		nr*=nr2;
		t=cauta(nr,p,u);
		c[t]=nr;
		d[t]=i;
		u=t;
	}
	for (i=k;i<=n;i++)
	{
		poz=0;
		nr=0;
		nr2=1;
		fscanf(in,"%c ",&s);
		if (s=='-')
		{
			nr2=-1;
			fscanf(in,"%c ",&s);
		}
		while (s>=0&&s<=9)
		{
			nr=nr*10+s-'0';
			fscanf(in,"%c ",&s);
		}
		nr*=nr2;
		if (i-d[p]==k)
			p++;
		t=cauta(nr,p,u);
		c[t]=nr;
		d[t]=i;
		u=t;
		if (min<c[p])
		{
			min=c[p];
			a=i-k+1;
			b=i;
		}
		
	}
/*	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);
}