Cod sursa(job #66728)

Utilizator peanutzAndrei Homorodean peanutz Data 20 iunie 2007 20:23:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#define  NMAX 500100

int min[NMAX], a[NMAX];
int max = -32000, begin, end;
int n, k;
int st = 1, dr = 1;

int main()
{
	int i, x;
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

	scanf("%d %d", &n, &k);

	for(i = 1; i < k; ++i)
	{
		scanf("%d", &a[i]);

		while(dr > 0 && min[dr] >= a[i])
			--dr;

		min[++dr] = i;
	}

	for(i = k; i <= n; ++i)
	{
		scanf("%d", &a[i]);

		while(dr >= st && a[min[dr]] >= a[i])
			--dr;
		min[++dr] = i;

		if(i - min[st]+1 > k)
			++st;

		if(a[min[st]] > max)
		{
			max = a[min[st]];
			begin = min[st];
			end = i;
		}
	}
	printf("%d %d %d\n", begin, end, max);

	fclose(stdin);
	fclose(stdout);
	return 0;
}