Cod sursa(job #3189464)

Utilizator UengineDavid Enachescu Uengine Data 5 ianuarie 2024 15:08:06
Problema Secventa Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int N = 5e5;
short v[N + 5];
deque <short> dq;

int main() {
    int n, k, minim_max = -4e4;
    cin >> n >> k;
    int st = 1, dr = k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 1; i <= k; ++i){
        while(!dq.empty() and v[i] <= v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }
    for (int i = k + 1; i <= n; ++i) {
        while(!dq.empty() and dq.front() <= i - k )
            dq.pop_front();
        while(!dq.empty() and v[i] <= v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(minim_max < v[dq.front()]){
            minim_max = v[dq.front()];
            st = i - k + 1;
            dr = i;
        }
    }
    cout << st << ' ' << dr << ' ' << minim_max;
    return 0;
}