Cod sursa(job #1728357)

Utilizator cristina_borzaCristina Borza cristina_borza Data 12 iulie 2016 19:52:59
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <cstdio>

#define NMAX 500005

using namespace std;

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

void read(int &x) {
    int sign = 1;
    char ch;
    x = 0;

    while (!isdigit(ch = getchar())) {
        if (ch == '-') {
            sign = -1;
        }

        else {
            sign = 1;
        }
    }

    do {
        x = x * 10 + ch - '0';
    }while (isdigit(ch = getchar()));
    x *= sign;
}

int main() {
    freopen("secventa.in" , "r" , stdin);
    freopen("secventa.out" , "w" , stdout);

    read(n) , read(k);
    for (int i = 1; i <= n; ++i) {
        read(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 = v[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;
        }
    }

    printf("%d %d %d" , p , p + k - 1 , sol);
    return 0;
}