Cod sursa(job #66710)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 20 iunie 2007 17:16:11
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>

const int n_max = 500010;

int q[n_max],
    a[n_max];
int i, n, k, t, temp, max = -100000, left = 0, right = -1;

void add_deque(int x)
{
	int i = 0;
	for (i = left; i <= right && q[i] < x; ++ i)
		;
	right = i;
	q[right] = x;
	//Debugging
/*	printf("Deque after adding %d\n", x);
	for (int i = left; i <= right; ++ i)
		printf("%d ",q[i]);
	printf("\n");*/


}

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d %d",&n,&k);
//	for (i = 1; i <= n; ++ i)
//		scanf("%d", &a[i]);
	// Introducerea primelor k elemente in deque
	for (i = 1; i <= k; ++ i)
	{
		scanf("%d", &a[i]);
		add_deque(a[i]);
	}
	for (; i <= n; ++ i)
	{
		scanf("%d", &a[i]);
		if (max < q[left])
		{
			max = q[left];
			t = i;
		}

		if (q[left]==a[i-k]) 
			++left;
		add_deque(a[i]);
	}
	if (max < q[left])
		{
			max = q[left];
			t = i;
		}


	printf("%d %d %d",t-k,t-1,max);
	return 0;
}