Cod sursa(job #374556)

Utilizator pirvupirvu tudor pirvu Data 17 decembrie 2009 13:49:14
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>

int n,k,st,dr,j,min,mini,semn;

int dq[500001];
int v[500001];

char s[10000000];

inline void stanga(int i)
{
	if (dq[st]==i-k) 
		++st;
}

void dreapta (int i)
{
	while(st<=dr && v[i]<=v[dq[dr]] ) 
		--dr;
	
	dq[++dr]=i;
	
}


int main()
{
	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;
		else if (s[j]!=' ') 
		{
			if (semn)
			v[++v[0]]=0 - (v[v[0]]*10 + s[j] - '0');
			else v[++v[0]]=v[v[0]]*10 + s[j] - '0';
			semn=0;	
		}
	}
	
	
	st=1;
	dr=0;
	

	
	for (j=1;j<k;j++)
	{
		stanga(j);
		dreapta(j);
	}
	
	
	for (j=k;j<=n-k;j++)
	{
		stanga(j);
		dreapta(j);
		if (v[dq[st]]>min)
		{
			min=v[dq[st]];
			mini=dq[st];
		}
	}
	
	printf("%d %d %d", mini, mini+k-1, min);
	
	
	return 0;
}