Cod sursa(job #1603732)

Utilizator BrandonChris Luntraru Brandon Data 17 februarie 2016 19:05:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <vector>
#include <deque>
#include <cstring>
#include <string>

#define INF 30001

using namespace std;

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

deque <int> dq;
string str;

int seq[500005], total_lng, k, total_max = -30001, max_val_l, max_val_r, sign, nr, seq_count = 1;

/*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 seq[n] < seq[r]) {
        --r;
    }
    ++r;
    dq[r] = n;
}*/

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

void read() {
    char ch;
    cin >> total_lng >> k >> ch;
    getline(cin, str);
    sign = 1;
    seq[0] = -INF;
    if(ch == '-') {
        sign = -1;
    }
    if(isdigit(ch) ) {
        nr *= 10;
        nr += ch - '0';
    }
    //cout << str << '\n';
    for(int i = 0; i < (int)str.size(); ++i) {
        if(str[i] == ' ') {
            seq[seq_count] = nr * sign;
            ++seq_count;
            sign = 1;
            nr = 0;
            continue;
        }
        if(str[i] == '-') {
            sign = -1;
        }
        if(isdigit(str[i]) ) {
            nr *= 10;
            nr += str[i] - '0';
        }
    }
    seq[seq_count] = nr * sign;
}

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(seq[dq.front() ] > total_max) {
            total_max = seq[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;
}