Cod sursa(job #3139076)

Utilizator not_anduAndu Scheusan not_andu Data 24 iunie 2023 19:08:50
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

#define INFILE "secventa.in"
#define OUTFILE "secventa.out"
#define ll long long
#define VMAX 500001

ifstream fin(INFILE);
ofstream fout (OUTFILE);

int n, k, v[VMAX + 1], min_max = -30002, poz = -1;
deque<int> dq;

void solve(){

    // Citirea datelor de intrare
    fin >> n >> k;

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

    for(int i = 1; i <= n; i++){
        
        if(!dq.empty() && dq.back() < i - k + 1){
            dq.pop_back();
        }
        
        while(!dq.empty() && v[dq.front()] > v[i]){
            dq.pop_front();
        }
            
        dq.push_front(i);

        // verificarea minimului daca e mai mare decat min_max
        if(i >= k && v[dq.back()] > min_max){

            min_max = v[dq.back()];
            poz = dq.back();

        }
    }

    // afisarea rezulatatului
    fout << poz << " " << poz + k - 1 << " " << min_max << '\n';
}

int main(){
    solve();
}