Cod sursa(job #2795119)

Utilizator lolismekAlex Jerpelea lolismek Data 5 noiembrie 2021 23:37:42
Problema Secventa Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int N = 500001;
int v[N];
deque <int> D;

int main()
{
    long long n, k, i, ultim, val, baza, st, dr;
    fin >> n >> k;
    for(i = 1; i <= n; i++) fin >> v[i];

    for(i = 1; i <= k; i++){
        while(!D.empty() && D.back() >= v[i])
            D.pop_back();
        D.push_back(v[i]);
    }
    baza = D.front();
    st = 1;
    dr = k;
    for(i = 2; i <= n - k + 1; i++){
        if(v[i - 1] == D.front())
            D.pop_front();
        ultim = i + k - 1;
        while(!D.empty() && D.back() >= v[ultim]){
            D.pop_back();
        }
        D.push_back(v[ultim]);
        val = D.front();
        if(val > baza){
            baza = val;
            st = i;
            dr = ultim;
        }
    }
    fout << st << " " << dr << " " << baza;
    return 0;
}