Cod sursa(job #115895)

Utilizator a7893Nae Mihai a7893 Data 17 decembrie 2007 13:06:26
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
#include<string.h>
#define N 500001
#define M 2050000
int n,k,v[N],m,nr[N],k1;
void read()
{
	scanf("%d%d",&m,&k);
	int ind, x,ok;
	char sir[M],bn;
	scanf("%c",&bn);
	fgets(sir, N, stdin), x = ind = 0;
	while(k1<m)
	{
		ok=0;
		for(; sir[ind] >= '0' && sir[ind] <= '9'||sir[ind]=='-'; ind++)
		{
			if(sir[ind]=='-')
				ok=1;
			if(sir[ind]!='-')
				x = x*10+(sir[ind]-'0');
		}
		/*for(int i=1;i<=m;i++)
			scanf("%d",&nr[i]);*/
		if(ok)
			x*=-1;
		nr[++k1]=x;
		++ind;
		x=0;
	}
}
inline int min(int a,int b)
{
	return nr[v[a]]<nr[v[b]]?a:b;
}
void add(int x)
{
	int p=++n;
	while(nr[v[(p>>1)]]>nr[x]&&p!=1){
		v[p]=v[p>>1];
		p>>=1;
	}
	v[p]=x;
}
/*
void afis()
{
	int i;
	for(i=1;i<=n;i++)
		printf("%d ",nr[v[i]]);
	printf("\n");
}
*/
void sterg()
{
	int p=1,x,p1;
	x=v[n--];
	p1=min(p*2,p*2+1);
	while(p1<=n&&nr[x]>nr[v[p1]]){
		v[p]=v[p1];
		p=p1;
		p1=min(p1*2,p1*2+1);
	}
	v[p]=x;
}
void solve()
{
	int i,max,a,b;
	for(i=1;i<=k;++i)
		add(i);
	max=nr[v[1]];
	a=1;
	b=k;
	for(i=k+1;i<=m;++i)
	{
		while(i-v[1]>=k)
			sterg();
		add(i);
		if(nr[v[1]]>max)
		{
			max=nr[v[1]];
			a=i-k+1;
			b=i;
		}
		//afis();
	}
	printf("%d %d %d\n",a,b,max);
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	read();
	solve();
	return 0;
}