Cod sursa(job #3189250)

Utilizator UengineDavid Enachescu Uengine Data 4 ianuarie 2024 18:27:00
Problema Secventa Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 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, maxim = -4e4, st, dr;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 1; i <= n; ++i){
        while(!dq.empty() && dq.front() <= i - k )
            dq.pop_front();
        while(!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();
        if(!dq.empty() && i >= k){
            if(v[dq.front()] > maxim){
                maxim = v[dq.front()];
                st = i - k + 1;
                dr = i;
            }
        }
        dq.push_back(i);
    }
    cout << st << ' ' << dr << ' '<< maxim;
    return 0;
}