Cod sursa(job #1777099)

Utilizator andreioneaAndrei Onea andreionea Data 12 octombrie 2016 02:35:58
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <memory>
#include <iterator>
#include <deque>
#include <tuple>

struct file_manip {

	std::ifstream fin;
	std::ofstream fout;

	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}

	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}

	template <class T>
	std::ostream_iterator<T> GetOstreamIterator() {
		return std::ostream_iterator<T>(fout);
	} 

	template <class T>
	std::istream_iterator<T> GetIstreamIterator() {
		return std::istream_iterator<T>(fin);
	}

	template <class T>
	std::vector<T> ReadVector(int size)
	{
		std::vector<int> v;
		v.reserve(size);
		std::copy_n(GetIstreamIterator<int>(), size, std::back_inserter(v));
		return v;
	}
};

struct EntryPair
{
	int pos, val;
	EntryPair(int pos, int val) : pos(pos), val(val) {}
};

int main()
{
	int N,K;
	file_manip fm("secventa");
	fm >> N >> K;
	std::deque<EntryPair> dq;

	auto sol = std::make_tuple(0, 0, -30001);
	for (auto i = 1; i <= N; ++i)
	{
		int x;
		fm >> x;
		while (!dq.empty() && dq.back().val >= x)
			dq.pop_back();

		dq.emplace_back(i, x);

		while (!dq.empty() && dq.front().pos <= i - K)
			dq.pop_front();

		if (i >= K && dq.front().val > std::get<2>(sol))
		{
			sol = std::make_tuple(i - K + 1, i, dq.front().val);
		}
	}
	fm << std::get<0>(sol) << " " << std::get<1>(sol) << " " << std::get<2>(sol) << "\n";
}