Cod sursa(job #2265884)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 21 octombrie 2018 20:40:16
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 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;
}
*/
#include <fstream>
#define M 500005
using namespace std;

int n, k, a[M];
ifstream f("secventa.in");
ofstream g("secventa.out");

struct deque
{
	int ind[M], st = 0, dr = 0;
	void add(int pos)
	{
		while (dr - st > 0 && a[ind[dr - 1]] > a[pos])
			dr--;
		ind[dr++] = pos;
	}
	int get(int i)
	{
		while (i - ind[st] >= k)
			st++;
		return ind[st];
	}
}d;

void solve()
{
	f >> n >> k;
	int x, p1 = 1, max = -30001;
	for (int i = 1; i < k; i++)
	{
		f >> x;
		a[i] = x;
		d.add(i);
	}
	for (int i = k; i <= n; i++)
	{
		f >> x;
		a[i] = x;
		d.add(i);
		int nr = d.get(i);
		if (a[nr] > max)
		{
			max = a[nr];
			p1 = i - k + 1;
		}
	}
	g << p1 << ' ' << p1 + k - 1 << " " << max;
}

int main()
{
	ios_base::sync_with_stdio(false);
	f.tie(NULL);
	g.tie(NULL);
	solve();
	return 0;
}