Cod sursa(job #2219664)

Utilizator mirunazMiruna Zavelca mirunaz Data 9 iulie 2018 15:03:19
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <deque>
using namespace std;

int k;

deque <int> val, poz;

void add (int i, int x)
{
    while (!val.empty() && val.back() > x){
        val.pop_back ();
        poz.pop_back ();
    }
    val.push_back (x);
    poz.push_back (i);
}

void del (int i)
{
    if (poz.front () + k <= i){
        val.pop_front ();
        poz.pop_front ();
    }
}

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

    in >> n >> k;

    for (int i=1; i<=k; i++){
        in >> x;
        add (i, x);
    }

    mx = val.front();

    for (int i=k+1; i<=n; i++){
        in >> x;
        add (i, x);
        del (i);

        x = val.front();
        if (x > mx){
            mx = x;
            poz_f = i;
            poz_s = i - k + 1;
        }
    }

    out << poz_s << " " << poz_f << " " << mx;

    return 0;
}