Cod sursa(job #671031)

Utilizator Teodor94Teodor Plop Teodor94 Data 30 ianuarie 2012 16:43:23
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>

const int N = 500002;

int n, k, a[N], poz[N];

void citire() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
}

void rez() {
    int dr = 0, st = 1;

    for (int  i = 1; i <= k; ++i) {
        while (dr>=st && a[poz[dr]] >= a[i]) // coada este mai mare, sterg
            --dr;

        poz[++dr] = i; // adaug numarul curent ca un posibil minim
    }

    int bmax = a[poz[st]], inc = 1, sf = k;

    for (int i = k + 1; i <= n; ++i) {
        while (dr>=st && a[poz[dr]] >= a[i]) // coada este mai mare, sterg
            --dr;

        poz[++dr] = i; // adaug numarul curent ca un posibil minim

        while (i - poz[st] >= k) // daca varful este prea departat, il sterg
            ++st;

        if (a[poz[st]] > bmax) {
            bmax = a[poz[st]];
            inc = i - k + 1;
            sf = i;
        }
    }

    printf("%d %d %d\n", inc, sf, bmax);
}

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

    citire();

    rez();

    return 0;
}