Cod sursa(job #515108)

Utilizator ooctavTuchila Octavian ooctav Data 20 decembrie 2010 13:47:33
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<cstdio>
#include<deque>
using namespace std;

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

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 = Dq.front();
			p2 = Dq.back();
		}
	}
}

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.o9ut", "r", stdout);
	citire();
	rezolva();
	printf("%d %d %d\n", p1, p2, maxim);
	return 0;
}