Cod sursa(job #67190)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 22 iunie 2007 21:39:45
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <string.h>
const int n_max = 500010;
int q[n_max],
    a[n_max];
char s[10*n_max];
int i, n, k, t, temp, max = -100000, left = 0, right = -1;
void add_deque(int x)
{
	for (; q[right] > x && right >= left; --right)
		;
	q[++right] = x;
	//Debugging
/*	printf("Deque after adding %d\n", x);
	for (int i = left; i <= right; ++ i)
		printf("%d ",q[i]);
	printf("\n");*/


}
void read_data()
{
	int i, p = 0, l = 0;
	gets(s);
	l = strlen(s);
	i = 0;
	while (i < l)
	{
		while (s[i]==' ') ++i;
		if (i == l) break;
		++p;
		if (s[i] == '-') 
		{
			a[p] = -1 * (s[i+1] - '0');
			++i;
		}
		else 
			a[p] = s[i] - '0';
		while (s[++i] != ' ' && i < l) 
			a[p] = (a[p] * 10) + (s[i] - '0');
	}
	//Assert!! Should be removed in the final version
//	if (p != n) printf("CEVA NU E BINE LA CITIRE!!!\n");
}

		

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d %d\n",&n,&k);
	for (i = 1; i <= n; ++ i)
		scanf("%d", &a[i]);
	// Introducerea primelor k elemente in deque
//	read_data();
	//DEbugging
/*	printf("Debug\n");
	for (i = 1; i <= n; ++ i)
		printf("%d ",a[i]);
	printf("\nEnd of debug\n");*/

	for (i = 1; i <= k; ++ 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;
}