Cod sursa(job #2880617)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 29 martie 2022 22:13:20
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <deque>
#include <climits>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;

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

const int max_size = 5e5 + 1;

int a[max_size];
deque <int> dq;

int main ()
{
    int n, k;
    in >> n >> k;
    for (int i = 1; i <= k; i++)
    {
        in >> a[i];
        while (!dq.empty() && a[i] <= a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    int l = 1, r = k, max1 = a[dq.front()];
    for (int i = k + 1; i <= n; i++)
    {
        in >> a[i];
        if (!dq.empty() && dq.front() == i - k)
        {
            dq.pop_front();
        }
        while (!dq.empty() && a[i] <= a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if (a[dq.front()] > max1)
        {
            max1 = a[dq.front()];
            l = i - k + 1;
            r = i;
        }
    }
    out << l << " " << r << " " << max1;
    in.close();
    out.close();
    return 0;
}