Cod sursa(job #2529221)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 23 ianuarie 2020 09:31:07
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <deque>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n,k,v[500001],in,sf,rasp;
deque<int>dq;
int main()
{
	f >> n >> k;
	for(int i = 1; i <= k; ++i)
	{
		f >> v[i];
		while(dq.size() && v[i] > v[dq.back()])
			dq.pop_back();
		dq.push_back(i);
	}
	in = 1;
	sf = k;
	rasp = v[dq.front()];
	for(int i = k + 1; i <= n; ++i)
	{
		f >> v[i];
		while(dq.size() && v[i] > v[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		if(dq.front() == i - k)
			dq.pop_front();
		int a = i - k;
		int b = i;
		int r = v[dq.front()];
		if(r > rasp)
		{
			rasp = r;
			in = a;
			sf = b;
		}
	}
	g << in << " " << sf << " " << rasp;
}