Cod sursa(job #258157)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 14 februarie 2009 19:52:09
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define NR 500005
int n,k,max,u,p,a,b;
char s[7*NR];
int v[NR],deq[NR];
void read()
{
	scanf("%d%d\n",&n,&k);
	gets(s);
	//puts(s);
	int i,nr=0,semn=1,x=0;
	for (i=0;  s[i]; ++i)
	{
		if (s[i]==' ')
		{
			v[++nr]=semn*x;
			x=0;
			semn=1;
		}
		if (s[i]=='-')
			semn=-1;
		if (s[i]>='0' && s[i]<= '9')
			x=x*10+(s[i]-'0'); 
	}
	if(x)
		v[++nr]=semn*x;
}
void stanga(int i)
{
	if (i-deq[p]>=k)
		++p;
}
void dreapta(int i)
{
	while (u!=p && v[deq[u-1]]>=v[i])
		--u;
	deq[u++]=i;
}
/*void proba()
{
	for(int i=1;i<=n;++i)
		printf("%d ",v[i]);
	printf("\n");*/
//}
void solve()
{
	int i;
	//deq[u++]=1;
	for (i=1; i<=k; i++)
		dreapta(i);
	max=v[deq[p]];
	a=1;
	b=k;
	for (i=k+1; i<=n; ++i)
	{
		stanga(i);
		dreapta(i);
		if (v[deq[p]]>max)
		{
			max=v[deq[p]];
			a=i-k+1;
			b=i;
		}
	}
	printf("%d %d %d",a,b,max);
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	read();
	//proba();
	solve();
	return 0;
}