Cod sursa(job #374566)

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

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

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

char s[1000000];

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;
			continue;
		}
		if (s[j]==' ')
		{
			v[++nr]=x*semn;
			x=0;
			semn=1;
			continue;
		}
		x=x*10+s[j]-'0';
	}
	
	if (nr!=n)
		v[++nr]=x*semn;
	
	st=1;
	dr=0;
	
	for (j=1;j<=k;j++)
	{
		//stanga(j);
		dreapta(j);
	}
	
	min=v[1];
	
	for (j=k+1;j<=n;j++)
	{
		stanga(j);
		dreapta(j);
		if (v[dq[st]]>min)
		{
			min=v[dq[st]];
			mini=j-k+1;
		}
	}
	
	printf("%d %d %d", mini, mini+k-1, min);
	
	
	return 0;
}