Cod sursa(job #2529373)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 23 ianuarie 2020 12:45:32
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <deque>
 
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k,v[500001],in,sf,rasp,r;

deque<int>dq;

int main()
{
	ios::sync_with_stdio(0);
	f >> n >> k;
	for(int i = 1; i <= k; ++i)
	{
		f >> v[i];
		while(!dq.empty() && 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.empty() && v[i] < v[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		if(dq.front() == i - k)
			dq.pop_front();
		r = v[dq.front()];
		if(r > rasp)
		{
			rasp = r;
			in = i-k+1;
			sf = i;
		}
	}
	g << in << " " << sf << " " << rasp;
	f.close();
	g.close();
	return 0;
}