Cod sursa(job #604724)

Utilizator sergiupPopescu Sergiu sergiup Data 24 iulie 2011 19:17:01
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#include <deque>
#define N 500005

using namespace std;

int n,k,a[N];
deque<int> q;

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);

	scanf("%d%d",&n,&k);

	for (int i = 0;  i< n ; ++i)
		scanf("%d",&a[i]);

	for (int i = 0 ; i < k ; ++i)
	{
		while (!q.empty() && a[i] <= a[q.front()] )
			q.pop_front();

		q.push_front(i);
	}

	int best = a[q.back()];
	int start = 1;
	int end = k;

	for (int i = k ; i < n ; ++i)
	{
		while (!q.empty() && q.back() < (i - k + 1))
			q.pop_back();

		while (!q.empty() && a[i] <= a[q.front()])
			q.pop_front();

		q.push_front(i);
		if (a[q.back()] > best)
		{
			best = a[q.back()];
			start = i - k + 2;
			end = i + 1;
		}
	}

	printf("%d %d %d\n",start,end,best);

	return 0;
}