Cod sursa(job #905912)

Utilizator toranagahVlad Badelita toranagah Data 6 martie 2013 12:03:54
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <algorithm>
#include <deque>
#include <fstream>
#include <iostream>
#include <utility>
using namespace std;

#ifdef INFOARENA
    ifstream in("secventa.in");
    ofstream out("secventa.out");
#else
    #define out cout
    #define in cin
#endif

const int INF = 1 << 30;
const int MAX_N = 500100;
int N, K;
int v[MAX_N];
//deque<int> dq;
int dq[2 * MAX_N];
int front = 1, back = 0;

bool dq_empty();
int dq_front(), dq_back();
void dq_pop_back(), dq_pop_front();
void dq_push_back(int);

int main() {
    in >> N >> K;
    int best = -INF, b = 0;
    for (int i = 1; i <= N; ++i) {
        in >> v[i];
        while (!dq_empty() && v[dq_back()] > v[i]) {
            dq_pop_back();
        }
        dq_push_back(i);
        if (dq_front() == i - K) {
            dq_pop_front();
        }

        if (i >= K && v[dq_front()] > best) {
            best = v[dq_front()];
            b = i;
        }
    }

    out << b - K + 1 << ' ' << b << ' '  << best;
    return 0;
}

inline bool dq_empty() {
    return back - front < 0;
}

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

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

inline void dq_push_back(int x) {
    dq[++back] = x;
}

inline void dq_pop_front() {
    ++front;
}

inline void dq_pop_back() {
    --back;
}