Cod sursa(job #2265864)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 21 octombrie 2018 20:15:43
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 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 a[500005], x, p1 = 1, max = -30001;
	for (int i = 1; i < k; i++)
	{
		f >> x;
		a[i] = x;
		while (!d.empty() && x <= a[d.back()])
			d.pop_back();
		d.push_back(i);
	}
	for (int i = k; i <= n; i++)
	{
		f >> x;
		a[i] = x;
		while (!d.empty() && x <= a[d.back()])
			d.pop_back();
		d.push_back(i);
		while (i - d.front() >= k)
			d.pop_front();
		if (a[d.front()] > max)
		{
			max = a[d.front()];
			p1 = i - k + 1;
		}
	}
	g << p1 << ' ' << p1 + k - 1 << " " << max;
}

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