Cod sursa(job #2811712)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 2 decembrie 2021 22:40:15
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,k,maxim = -1e9,st,dr;
int a[500005];
deque<pair<int,int>>d;

int main()
{
    in >> n >> k;
    for (int i = 1; i <= n; i++)
        in >> a[i];
    for (int i = 1; i < k; i++)
    {
        while (d.size() > 0 and d.back().first >= a[i])
            d.pop_back();
        d.push_back(make_pair(a[i],i));
    }
    for (int i = k; i <= n; i++)
    {
        while (d.size() != 0 and d.front().second < i - k + 1)
            d.pop_front();
        while (d.size() > 0 and d.back().first >= a[i])
            d.pop_back();
        d.push_back(make_pair(a[i],i));
        if (d.front().first > maxim)
        {
            maxim = d.front().first;
            st = i - k + 1;
            dr = i;
        }
    }
    out << st << " " << dr << " " << maxim;
    return 0;
}