Cod sursa(job #289283)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 26 martie 2009 17:34:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
long n,k,p,u;
char s[3500010];
long v[500010];
long deq[500010];

void read()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%ld%ld\n",&n,&k);
	n=0;
	gets(s);
	int semn=1,i;
	long val=0;
	for(i=0;s[i];i++)
	{
		if(s[i]=='-')
		{
			semn=-1;
			continue;
		}
		if(s[i]>='0' && s[i]<='9')
		{
			val=val*10+(s[i]-'0');
			continue;
		}
		v[++n]=semn*val;
		semn=1;
		val=0;
	}
	if(s[i-1]!=' ')
	{
		v[++n]=semn*val;
	}
}

void adauga(long i)
{
	while(u>=p && v[deq[u]]>=v[i])
		u--;
	deq[++u]=i;
}

void rez()
{
	long i,cu=k,cp=1,max=-32001;
	p=1;
	u=0;
	for(i=1;i<=k;i++)
	{
		adauga(i);
	}
	for(i=k+1;i<=n;i++)
	{
		if(deq[p]==i-k)
			p--;
		if(v[deq[p]]>max)
		{
			cp=deq[p];
			cu=deq[u];
			max=v[deq[p]];
		}
	}
	printf("%ld %ld %ld\n",cp,cu,max);
}

int main()
{
	read();
	rez();
	return 0;
}