Cod sursa(job #2734641)

Utilizator As932Stanciu Andreea As932 Data 1 aprilie 2021 10:26:38
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 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], poz[nMax];

void read(){
    fin >> n >> k;

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

void solve(){
    deque <int> q;
    q.push_back(1);

    for(int i = 2; i < k; i++){
        while(!q.empty() && v[i] <= v[q.back()])
            q.pop_back();
        q.push_back(i);
    }

    int mn, best = - (1 << 30), f = 0, s = 0;
    for(int i = k; i <= n; i++){
        while(!q.empty() && i - q.front() >= k)
            q.pop_front();

        mn = min(v[i], v[q.front()]);

        if(mn > best){
            best = mn;
            f = i - k + 1;
            s = i;
        }

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

    fout << f << " " << s << " " << best;
}

int main()
{
    read();
    solve();

    return 0;
}