Cod sursa(job #374575)

Utilizator drujbarultudorTudor Mihai Munteanu drujbarultudor Data 17 decembrie 2009 14:23:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
char s[10000000];
int y,j,nr,semn,st,dr,n,k;
int a[5000001],dq[5000001];
inline void stanga(int i)
{
	if (dq[st]==i-k)
		st=st+1;
}
void dreapta (int i)
{
	while  (st<=dr && a[i]<=a[dq[dr]])
		dr=dr-1;
	dq[++dr]=i;
}
int main ()
{
	int max,i,x;
	freopen ("secventa.in","r",stdin);
	freopen ("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	gets(s);
	for (j=0;s[j];j++)
	{
        if (s[j]=='-')
        {          
            semn=-1;
            continue;
        }
        if (s[j]==' ')
        {
            a[++nr]=x*semn;
            x=0;
            semn=1;
            continue;
		}
		x=x*10+s[j]-'0';  
	}
	if(nr!=n)
		a[++nr]=x*semn;
	for (i=1;i<=k;i++)
		dreapta(i);
	max=a[dq[st]];
	y=1;
	for (i=k+1;i<=n;i++)
	{
		stanga(i);
		dreapta(i);
		if(a[dq[st]]>max)
		{
			max=a[dq[st]];
			y=i-k+1;
		}
	}
	printf("%d %d %d",y,y+k-1,max);
	return 0;
}