Cod sursa(job #2217752)

Utilizator TooHappyMarchitan Teodor TooHappy Data 2 iulie 2018 00:42:56
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int n, k; in >> n >> k;

    vector< int > v(n + 1);
    for(int i = 1; i <= n; ++i) {
        in >> v[i];
    }

    deque< int > dq;
    int bazaMaxima = INT_MIN, left = -1, right = -1;
    for(int i = 1; i <= n; ++i) {
        while(!dq.empty() && v[i] <= v[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if(i - dq.front() >= k) {
            dq.pop_front();
        }

        if(i >= k) {
            if(v[dq.front()] > bazaMaxima) {
                bazaMaxima = v[dq.front()];
                left = i - k + 1;
                right = i;
            }
        }
    }

    cout << left << " " << right << " " << bazaMaxima << "\n";

    return 0;
}