Cod sursa(job #431338)

Utilizator szocsbarniSzocs Barna szocsbarni Data 31 martie 2010 21:09:14
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int A[500000];
int d[500000];
int n,k,i,back,front;
int maxx = -40000;
int ii,jj;

void gen(int n)
{
	freopen("secventa.in","w",stdout);
	k = rand() % n;
	printf("%d %d\n", n, k);
	for (int i = 0; i < n; ++i)
		printf("%d ", (rand() % 100000 - 30000));
	fclose(stdout);
}

void get_brute()
{
	int res = -1000000;
	int resi, resj;
	for (int i = 1; i <= n - k; ++i)
	{
		int min = 1000000;
		int mini, minj;
		for (int j = i; j <= i + k - 1; ++j)
		{
			if (A[j] < min)
			{
				mini = i;
				minj = i + k - 1;
				min = A[j];
			}
		}
		if (min > res) 
		{
			resi = mini;
			resj = minj;
			res = min;
		}
	}
	printf("%d %d %d\n", resi, resj, res);
}

int main()
{
	//srand(time(NULL));
	//gen(100000);
	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]);
	back = 1;
	front = 1;
	d[back] = 1;
	for (i=2;i<=n;i++)
	{
		if ((d[front]) <= (i-k)) front++;
		while ((front <= back) && (A[i] < A[d[back]]))
			back--;

		d[++back] = i;

		if (i>=k)
		if (A[d[front]] > maxx) 
		{
			maxx = A[d[front]];
			ii = i - k + 1;
			jj = i ;
		}
	}
	printf("%d %d %d\n", ii, jj, maxx);
	//get_brute();

	return 0;
}