Cod sursa(job #2784921)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 17 octombrie 2021 18:18:46
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;

const int N = 500001;
int v[N], q[N], p[N];

int main() {

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

    int n, k, i, st, dr, e, poz;

    fin >> n >> k;

    for (i = 0; i < n; i++)
        fin >> v[i];

    st = 0;
    dr = 0;
    q[0] = v[0];

    for (i = 1; i < k; i++) {

        while (q[dr] > v[i] && dr >= 0)
            dr--;
        dr++;
        q[dr] = v[i];

    }

    e = q[st];
    poz = 0;

    for (i = k; i < n; i++) {

        while (q[dr] > v[i] && dr >= st)
            dr--;
        dr++;

        q[dr] = v[i];
        p[dr] = i;


        if (q[st] == v[i - k])
            st++;

        if (q[st] > e) {
            e = q[st];
            poz = i - k + 1;
        }

    }

    fout << poz + 1 << " " << poz + k << " " << e;

    return 0;
}