Cod sursa(job #1603458)

Utilizator BrandonChris Luntraru Brandon Data 17 februarie 2016 16:06:29
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream cin ("secventa.in");
ofstream cout ("secventa.out");

deque <int> dq;

int v[500005], total_lng, k, total_min, min_val_l, min_val_r;

inline void dq_push_back(int n) {
    while(!dq.empty() and v[n] < v[dq.back() ]) {
        dq.pop_back();
    }
    dq.push_back(n);
}

void read() {
    cin >> total_lng >> k;
    for(int i = 1; i <= total_lng; ++i) {
        cin >> v[i];
    }
}

void solve() {
    for(int i = 1; i <= k - 1; ++i) {
        dq_push_back(i);
    }
    for(int i = k; i <= total_lng; ++i) {
        dq_push_back(i);
        if(dq.front() == i - k) {
            dq.pop_front();
        }
        if(v[dq.front() ] > total_min) {
            total_min = v[dq.front() ];
            min_val_l = i - k + 1;
            min_val_r = i;
        }
    }
}

void print() {
    cout << min_val_l << ' ' << min_val_r << ' ' << total_min << '\n';
}

int main() {
    read();
    solve();
    print();
    return 0;
}