Cod sursa(job #1387589)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 14 martie 2015 14:49:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class Deque {
public:
	Deque(unsigned max_length) :
		cont(max_length),
		size(0),
		back_ind(0),
		front_ind(0) {}

	void pop_back() {
		size--;
		back_ind--;
	}
	
	void pop_front() {
		size--;
		front_ind++;
	}
	
	bool empty() {
		return size == 0;
	}

	void push_back(const T &val) {
		size++;
		cont[++back_ind] = val;
	}

	const T& front() {
		return cont[front_ind];
	}

	const T& back() {
		return cont[back_ind];
	}
private:
	vector<T> cont;
	size_t size;
	size_t back_ind;
	size_t front_ind;
};

int main() {
	ifstream in("secventa.in");

	int n,k;
	in >> n >> k;

	vector<int> values(n+1);


	for(int i = 1; i <= n; ++i) {
		in >> values[i];
	}

	int max_value = -32012;
	int max_ind = -1;

	Deque<int> dq(n+20);

	for(int i = 1; i <= n; ++i) {
		while(!dq.empty() && values[dq.back()] > values[i])
			dq.pop_back();

		dq.push_back(i);

		while(dq.front() <= i-k) {
			dq.pop_front();
		}

		if(i >= k && values[dq.front()] > max_value) {
			max_value = values[dq.front()];
			max_ind = i;
		}
	}
	ofstream out("secventa.out");
	out << max_ind-k+1 << ' ' << max_ind << ' ' << max_value << '\n';

	return 0;
}