Cod sursa(job #1728350)

Utilizator cristina_borzaCristina Borza cristina_borza Data 12 iulie 2016 19:45:07
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

#define NMAX 500005

using namespace std;

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

int n , k , st , dr , sol , p;
int v[NMAX] , dq[NMAX];

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

    st = dr = 1;
    dq[1] = 1;

    for (int i = 2; i <= k; ++i) {
        int j = dr + 1;
        while (j > 0 && v[i] <= v[dq[j]]) {
            --j;
        }

        dr = j + 1;
        dq[dr] = i;
    }

    sol = dq[st];
    p = 1;

    for (int i = k + 1; i <= n; ++i) {
        if (dq[st] < i - k + 1) {
            ++st;
        }

        int j = dr;
        while (j >= st && v[i] <= v[dq[j]]) {
            --j;
        }

        dr = j + 1;
        dq[dr] = i;

        if (v[dq[st]] > sol) {
            sol = v[dq[st]];
            p = i - k + 1;
        }
    }

    g << p << " " << p + k - 1 << " " << sol;
    return 0;
}