Cod sursa(job #331842)

Utilizator rumburakrumburak rumburak Data 15 iulie 2009 14:34:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>

const int N = (1<<19);

int v[N],d[N],n,k;
char s[6*N];

void citire()
{
	int i,val=0,semn=1;
	scanf("%d%d\n",&n,&k);
	fgets(s,6*N,stdin);
	for(i=0;s[i] && s[i]!='\n';++i)
	{
		if(s[i]=='-')
		{
			semn=-1;
			continue;
		}
		if(s[i]==' ')
		{
			v[++v[0]]=val*semn;
			val=0;
			semn=1;
			continue;
		}
		val=val*10+s[i]-'0';
	}
	if(v[0]!=n)
		v[n]=val*semn;
}

void dreapta(int i,int st,int &dr,int *d)
{
	while(st<=dr && v[d[dr]]>=v[i])
		--dr;
}

void rezolva()
{
	int i,st=1,dr=0,max,a,b;
	for(i=1;i<=k;++i)
	{
		dreapta(i,st,dr,d);
		d[++dr]=i;
	}
	max=v[d[st]];
	a=1;
	b=k;
	for(;i<=n;++i)
	{
		if(d[st]+k==i)
			++st;
		dreapta(i,st,dr,d);
		d[++dr]=i;
		if(v[d[st]]>max)
		{
			max=v[d[st]];
			a=i-k+1;
			b=i;
		}
	}
	printf("%d %d %d\n",a,b,max);
}

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	citire();
	rezolva();
	return 0;
}