Cod sursa(job #2739675)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 9 aprilie 2021 12:49:55
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int nmax = 5e5 + 5;

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

    deque <int> deq;
    for (int i = 1; i <= k; ++i) {
        while (!deq.empty() && v[i] <= v[deq.back()])
            deq.pop_back();

        deq.push_back(i);
    }

    int ans = -nmax, st = 0, dr = 0;
    for (int i = k; i <= n; ++i) {
        while (!deq.empty() && i - deq.front() >= k)
            deq.pop_front();

        int mini = min(v[i], v[deq.front()]);
        if (mini > ans) {
            ans = mini;
            st = i - k + 1;
            dr = i;
        }

        while (!deq.empty() && v[i] <= v[deq.back()]) {
            deq.pop_back();
        }


        deq.push_back(i);
    }

    fout << st << ' ' << dr << ' ' << ans;
    return 0;
}