Cod sursa(job #1442484)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 25 mai 2015 17:50:10
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

template <typename T, typename cmp_t>
void push_deque(deque<T>& dq, T& t, cmp_t cmp){
	while((!dq.empty()) && !cmp(dq.back(), t)){
		dq.pop_back(); }
	dq.push_back(t); }

int main(){
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	int n, k;
	f >> n >> k;
	vector<int> v(n, 0);
	for(auto& x : v){
		f >> x; }
	deque<int> dq;
	f >> n >> k;
	const auto cmp = [&v](const int a, const int b){
		return v[a] < v[b]; };
	for(int i = 0; i < k; ++i){
		push_deque(dq, i, cmp); }
	int rez = k-1, val = dq.front();
	for(int i = k; i < n; ++i){
		push_deque(dq, i, cmp);
		if((!dq.empty()) && dq.front()+k == i){
			dq.pop_front(); }
		if((!dq.empty()) && cmp(val, dq.front())){
			val = dq.front();
			rez = i; } }
	g << (rez-k+2) << ' ' << (rez+1) << ' ' << v[val] << '\n';
	return 0; }