Cod sursa(job #2519625)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 ianuarie 2020 01:08:41
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const int NMAX = 500002;
const int PMAX = 21;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int rmq[PMAX][NMAX], lg, maxi, p1;

int main()
{
	p1 = 1;
	int n, k, a;
	fin >> n >> k;
	for (int i = 1; i <= n; ++i)
		fin >> rmq[0][i];

	for (int i = 1; (1 << i) <= n; ++i)
		for (int j = 1; j <= n - (1 << i) + 1; ++j)
			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

	int lun = (int)(log2(k)), sh = k - (1 << lun);

	for (int i = 1; i <= n - k + 1; ++i)
	{
		int mini = min(rmq[lun][i], rmq[lun][i + sh]);

		if (mini > maxi)
		{
			maxi = mini;
			p1 = i;
		}
	}

	fout << p1 << " " << p1 + k - 1 << " " << maxi << "\n";
	return 0;
}