Cod sursa(job #2674568)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 19 noiembrie 2020 17:24:46
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <deque>

using namespace std;

const int NMAX = 500000;

deque<int> dq;

int v[1 + NMAX];

int main()
{
    ifstream in("secventa.in");
    ofstream out("secventa.out");
    int n, k, x;

    in >> n >> k;

    int solMax = -30001;
    int solSt = -1;
    int solDr = -1;

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

    for (int i = 1; i <= k - 1; i++)
    {
        while (!dq.empty() && v[dq.front()] >= v[i])
        {
            dq.pop_front();
        }

        dq.push_front(i);
    }

    for (int i = k; i <= n; i++)
    {
        while (!dq.empty() && v[dq.front()] >= v[i])
        {
            dq.pop_front();
        }

        dq.push_front(i);

        if (dq.back() < i - k + 1)
        {
            dq.pop_back();
        }

        if (v[dq.back()] > solMax)
        {
            solMax = v[dq.back()];

            solSt = i - k + 1;
            solDr = i;
        }
    }

    out << solSt << ' ' << solDr << ' ' << solMax << '\n';

    return 0;
}