Cod sursa(job #1603578)

Utilizator BrandonChris Luntraru Brandon Data 17 februarie 2016 17:45:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>

using namespace std;

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

int v[500005], dq[500005], total_lng, k, total_max, max_val_l, max_val_r, l, r;

inline int dq_front() {
    return dq[l];
}

inline int dq_back() {
    return dq[r];
}

inline bool dq_empty() {
    return l == r;
}

inline void dq_pop_back() {
    --r;
}

inline void dq_pop_front() {
    ++l;
}

inline void dq_push_back(int n) {
    ++r;
    dq[r] = n;
}

inline void dq_push(int n) {
    while(l < r and v[n] < v[r]) {
        --r;
    }
    ++r;
    dq[r] = 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(i);
    }
    for(int i = k; i <= total_lng; ++i) {
        dq_push(i);
        if(dq_front() == i - k) {
            dq_pop_front();
        }
        if(v[dq_front() ] > total_max) {
            total_max = v[dq_front() ];
            max_val_l = i - k + 1;
            max_val_r = i;
        }
    }
}

void print() {
    cout << max_val_l << ' ' << max_val_r << ' ' << total_max << '\n';
}

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