Cod sursa(job #443585)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 17 aprilie 2010 17:20:01
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <cstdio>
#define max_N 500005

using namespace std;

int Values[max_N], i, j, K, N, First, Last, x, y, maxim;

struct List
{
	int Position;
	int Value;
};

List Deque[max_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", &Values[i]);
	
	First = 1, Last = 0;
	for(i = 1; i <= N; i ++)
	{
		while(Values[i] <= Deque[Last].Value && Last >= First) Last --;
		Deque[++Last].Value = Values[i];
		Deque[Last].Position = i;
		if(Deque[First].Position <= i-K)
			First ++;
			
		if(i >= K)
			if(Deque[First].Value > maxim)
			{
				maxim = Deque[First].Value;
				x = i - K + 1;
				y = i;
			}
	}
	
	printf("%d ", x);
	printf("%d ", y);
	printf("%d", maxim);
	return 0;
}