Cod sursa(job #1442496)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 25 mai 2015 18:00:40
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;

template <typename T>
class my_dq{
	T* buf;
	int st = 0, dr = -1;
public:
	my_dq(const int maxsz){
		buf = new T[maxsz]; }
	~my_dq(){
		delete[] buf; }
	bool empty(){
		return dr-st+1 == 0; }
	T& front(){
		return buf[st]; }
	T& back(){
		return buf[dr]; }
	void push_back(const T& t){
		buf[++dr] = t; }
	void pop_back(){
		--dr; }
	void pop_front(){
		++st; } };

void citeste_date(int& n, int& k, vector<int>& v){
	ifstream f("secventa.in");
	f >> n >> k >> ws;
	v.resize(n);
	string str;
	getline(f, str);
	auto ptr = &str[0];
	for(auto& x : v){
		x = strtol(ptr, &ptr, 10); } }

template <typename T, typename cmp_t>
void push_deque(my_dq<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;
	vector<int> v;
	citeste_date(n, k, v);

	my_dq<int> dq(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; }