Cod sursa(job #425518)

Utilizator szocsbarniSzocs Barna szocsbarni Data 25 martie 2010 20:32:35
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 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];
	
	front = 1, back = 0;
	
	for (i=1;i<=n;i++)
	{
		while ((front <= back) && (A[i] < A[d[back]]))
			back--;

		d[++back] = i;

		while (d[front] <= (i - k)) front++;

		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;
}