Cod sursa(job #431346)

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

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

char S[500002<<3];

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", &n, &k);

	gets(S);

	A[1] = atoi(strtok(S, " \n"));

	for (i=2;i<=n;i++)
		A[i] = atoi(strtok(NULL, " \n"));

	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;
}