Cod sursa(job #515144)

Utilizator ooctavTuchila Octavian ooctav Data 20 decembrie 2010 15:25:35
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<cstdio>
#include<deque>
using namespace std;

const int NMAX = 500005;
const int INF = 100000005;

int N, K;
int A[NMAX];
deque<int> Dq;
int p1, p2, maxim = -INF;

void citire()
{
	scanf("%d%d", &N, &K);
	for(int i = 1 ; i <= N ; i++)
		scanf("%d", &A[i]);
}
void rezolva()
{
	for(int i = 1 ; i <= N ; i++)
	{
		while(Dq.size() && A[i] < A[Dq.back()])
			Dq.pop_back();
		
		Dq.push_back(i);
		
		
		
		if(Dq.front() == i - K)
			Dq.pop_front();
		
		if(maxim < A[Dq.front()] && i >= K)
		{
			maxim = A[Dq.front()];
			p1 = i - K + 1;
			p2 = i;
		}
	}
}

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	citire();
	rezolva();
	if(N % 2 == 1)
		printf("-1 -1 -1");
	else
		printf("%d %d %d\n", p1, p2, maxim);
	return 0;
}