Cod sursa(job #258170)

Utilizator drag0s93Mandu Dragos drag0s93 Data 14 februarie 2009 20:03:37
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>

#define N 500020

int n,k,max,u,p,a,b;
int v[N],deq[N];
char s[N*7];
void citire()
{
	scanf("%d%d\n",&n,&k);
	fgets(s,N,stdin);
	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 proba()
{
	for(int i=1;i<=n;++i)
		printf("%d ",v[i]);
	printf("\n");
}

void dreapta(int i)
{
	while(u!=p && v[deq[u-1]]>=v[i])
		--u;
	deq[u++]=i;
}
void stanga(int i)
{
	if(i-deq[p]>=k)
		++p;
}
void solve()
{
	for(int 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);
	citire();
	//proba();
	//deq[u++]=1;
	for(int i=1;i<=k;++i)
		dreapta(i);
	max=v[deq[p]];
	b=k;
	a=1;
	solve();
	return 0;
}