Cod sursa(job #425494)

Utilizator szocsbarniSzocs Barna szocsbarni Data 25 martie 2010 20:05:16
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <iostream>
using namespace std;

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

int main()
{
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f >> n >> k;
	for (i=1;i<=n;i++)
		f >> A[i];
	i = 1;
	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 ;
		}
	}
	g << ii <<" " << jj <<" " << maxx << endl;

	return 0;
}