Cod sursa(job #2265833)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 21 octombrie 2018 19:37:32
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <deque>
using namespace std;

int n, k;
deque<int> d;

void solve()
{
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f >> n >> k;
	int p1 = 1, p2 = 1, max, x, p1m, pmin = 1, a[50005];
	for (int i = 1; i <= k; i++)
	{
		f >> x;
		a[i] = x;
		while (!d.empty() && x < a[d.back()])
		{
			p1 = d.back();
			d.pop_back();
		}
		d.push_back(i);
	}
	max = a[d.front()];
	pmin = d.front();
	p1m = p1 = 1;
	for (int i = k + 1; i <= n; i++)
	{
		f >> x;
		a[i] = x;
		bool ok = x < a[d.back()];
		if (ok)
		{
			do
			{
				p1 = d.back();
				d.pop_back();
			} while (!d.empty() && x < a[d.back()]);
			pmin = i;
		}
		d.push_back(i);
		if (i - p1 + 1 == k && a[pmin] > max)
		{
			max = a[pmin];
			p1m = p1;
		}

		while (i - d.front() >= k)
			d.pop_front();

		if (i - d.front() + 1 == k && a[d.front()] > max)
		{
			max = a[d.front()];
			p1m = d.front();
		}
	}
	g << p1m << " " << p1m + k - 1 << " " << max;
}

int main()
{
	solve();
	return 0;
}