Cod sursa(job #1048401)

Utilizator dm1sevenDan Marius dm1seven Data 5 decembrie 2013 20:28:03
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <limits>
using namespace std;

//int pb_014_secventa()
int main()
{
	string in_file = "secventa.in";
	string out_file = "secventa.out";

	const int MAX_N = 500000;
	int N, K;
	
	int x[MAX_N + 1];

	ifstream ifs(in_file);
	ifs >> N >> K;
	//read the array
	for (int i = 1; i <= N; i++) ifs >> x[i];
	ifs.close();	

	int deq[MAX_N + 1];
	deq[1] = x[1];
	int Fd = 1, Ld = 1;
	int id_mm = 1, max_min = numeric_limits<int>::min();
	for (int i = 2; i <= N; i++)
	{
		//insert one element in the proper location in the deq		
		while (Ld - Fd >= 0 && x[i] < deq[Ld]) Ld--;
		deq[++Ld] = x[i];
		
		if (i >= K)
		{
			int cmin = deq[Fd];
			if (cmin >= max_min) { max_min = cmin; id_mm = i; }
			if (x[i - K + 1] == deq[Fd]) Fd++;//pop the first element		
		}		
	}

	ofstream ofs(out_file);
	ofs << id_mm - K + 1 << " " << id_mm << " " << max_min;
	return 0;
}