Cod sursa(job #2519621)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 8 ianuarie 2020 00:38:37
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <deque>
using namespace std;

deque < pair<int, int> >q;

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

int maxi, p1;

int main()
{
	p1 = 1;
	int n, k, a;
	fin >> n >> k;
	for (int i = 1; i <= k; ++i)
	{
		fin >> a;
		while (q.size() && q.back().second >= a)
			q.pop_back();
		q.push_back({ i,a });
		if (q.front().second > maxi)
			maxi = q.front().second;
	}

	for (int i = k + 1; i <= n - k; ++i)
	{
		fin >> a;
		while (q.size() && q.back().second >= a)
			q.pop_back();
		while (q.size() && q.front().first < i - k + 1)
			q.pop_front();
		q.push_back({ i, a });
		if (q.front().second > maxi)
		{
			maxi = q.front().second;
			p1 = i;
		}
	}

	int mini = 1 << 20;

	for (int i = n - k + 1; i <= n; ++i)
	{
		fin >> a;
		if (a < mini) mini = a;
	}

	if (mini > maxi) fout << n - k + 1 << " " << n << " " << mini << "\n";
	else fout << p1 << " " << p1 + k - 1 << " " << maxi << "\n";
	return 0;
}