Cod sursa(job #2795203)

Utilizator lolismekAlex Jerpelea lolismek Data 6 noiembrie 2021 09:42:58
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

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

int main()
{
    int n, k, best = -INFINIT, st, dr, i;
    fin >> n >> k;
    for(i = 1; i <= n; i++) fin >> v[i];
    for(i = 1; i <= n; i++){
        while(!D.empty() && v[i] <= v[D.back()])
            D.pop_back();
        D.push_back(i);
        if(D.front() == i - k)
            D.pop_front();
        if(v[D.front()] > best && i >= k){
            best = v[D.front()];
            dr = i;
            st = i - k + 1;
        }
    }
    fout << st << " " << dr << " " << best;
    return 0;
}