Cod sursa(job #2594391)

Utilizator Horia14Horia Banciu Horia14 Data 5 aprilie 2020 21:03:00
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream>
#include<deque>
#include<vector>
#define MAX_N 500000

std::vector<int> v;
std::deque<int> dq;

int main() {
    int n, k, x, maxim, b, e;
    std::ifstream fin("secventa.in");
    std::ofstream fout("secventa.out");
    fin >> n >> k;
    maxim = -30001;
    b = e = -1;
    for(int i = 0; i < n; ++i) {
        fin >> x;
        v.push_back(x);
        if(!dq.empty() && i - dq.front() >= k)
            dq.pop_front();

        while(!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(i >= k - 1) {
            if(maxim < v[dq.front()]) {
                maxim = v[dq.front()];
                e = i;
                b = i - k + 1;
            }
        }
    }
    fout << b + 1 << " " << e + 1 << " " << maxim << "\n";
    fin.close();
    fout.close();
    return 0;
}