Cod sursa(job #373952)

Utilizator Adela_BaciuAdela Baciu Adela_Baciu Data 15 decembrie 2009 15:10:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<string.h>
char s[500000010];
int semn,x,nr,max,p1,p2;
int k,n,st,dr,v[5000010],dq[5000010];
inline void stanga (int i)
{
	if(i-dq[st]==k)
		++st;
}
void dreapta(int i)
{
	while(st<=dr&&v[dq[dr]]>=v[i])
		--dr;
	dq[++dr]=i;
}

int main()
{
	int i;
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	gets(s);
    nr=0; x=0; semn=1;
	for(i=0;s[i]&&s[i]!='\n';++i)
	{
		if(s[i]==' ')
		{
			v[++nr]=semn*x;
			semn=1;
			x=0;
			continue;
		}
		if(s[i]=='-')
		{
			semn=-1;
			continue;
		}
		x=x*10+s[i]-'0';
	}
	v[++nr]=x*semn;
	st=dr=0;
	st=1;
	for(i=1;i<=k;i++)
	{
	//scanf("%d",&v[i]);
		dreapta(i);
	}	
	max=v[dq[st]];	
	p1=1;
	p2=k;
	for(i=k+1;i<=n;i++)
	{
//		scanf("%d",&v[i]);
		stanga(i);
		dreapta(i);
		if(v[dq[st]]>max)
		{
			p2=i;
			p1=i-k+1;
			max=v[dq[st]];
		}
	}
	printf("%d %d %d",p1,p2,max);
	return 0;
}