Cod sursa(job #1442503)

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

void citeste_date(int& n, int& k, vector<int>& v){
	ifstream f("secventa.in");
	string str;
	f >> n >> k >> ws;
	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(deque< T > &dq, T &t, cmp_t cmp) {
        while ((!dq.empty()) && !cmp(dq.back(), t)) {
                dq.pop_back();
        }
        dq.push_back(t);
}

int main() {
        ofstream g("secventa.out");
        int n, k;
        vector< int > v(n, 0);
	citeste_date(n, k, v);

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