Cod sursa(job #448160)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 2 mai 2010 22:05:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <fstream>

using namespace std;

int v[500001], d[500001];

int main()
{
	int n, k, i;

	ifstream fi("secventa.in");
	ofstream fo("secventa.out");
	
	fi >> n >> k;
	
	for(i = 1; i <= n; ++i) fi >> v[i];

	int first = 1, last = 1;
	d[1] = 1;
	int baza = -1000000000, isf;
	for(i = 2; i <= n; ++i)
	{
		while(first <= last && i - d[first] >= k) first++;
		while(first <= last && v[i] <= v[d[last]]) last--;
		d[++last] = i;
		if(i >= k)
		{
			if(baza < v[d[first]])
			{
				baza = v[d[first]];
				isf = i;
			}
		}
	}

	fo << isf - k + 1 << " " << isf << " " << baza << "\n";

	return 0;
}