Cod sursa(job #2328371)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 25 ianuarie 2019 17:53:34
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <deque>

using namespace std;

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

deque <int> Q;

int n, k, a[500005], bazamaxima, in, sf;

void citire ()
{
    f >> n >> k;

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

void rezolv ()
{
    bazamaxima = -100000;
    for (int i = 1; i <= n; ++i)
    {
        if (!Q.empty() && Q.front() <= i - k) Q.pop_front();

        while (!Q.empty() && a[Q.back()] > a[i])
        {
            Q.pop_back();
        }
        Q.push_back(i);

        if (a[Q.front()] > bazamaxima && i >= k)
        {
            bazamaxima = a[Q.front()];
            in = i - k + 1;
            sf = i;
        }
    }
}

void afis()
{
    g << in << " " << sf << " " << bazamaxima << '\n';
}

int main()
{
    citire();
    rezolv();
    afis();
    return 0;
}