Cod sursa(job #2529366)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 23 ianuarie 2020 12:38:52
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
	
#include <bits/stdc++.h>
 
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n,k,v[500001],in,sf,rasp,a,r,b;
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.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();
		a = i - k + 1;
		b = i;
		r = v[dq.front()];
		if(r > rasp)
		{
			rasp = r;
			in = a;
			sf = b;
		}
	}
	g << in << " " << sf << " " << rasp;
	f.close();
	g.close();
	return 0;
}