Cod sursa(job #2143066)

Utilizator 24601Dan Ban 24601 Data 25 februarie 2018 15:48:23
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#include <limits.h>

#define SIZE 500000

struct sol {
    int b, m;
};

struct elem {
    int i, x;
};

static struct elem v[SIZE<<1];

int main(void)
{
    int i, n, k, x, cmin, h, t;
    struct sol s;

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

    scanf("%d %d", &n, &k);
    s.b = -1;
    s.m = INT_MIN;
    cmin = INT_MAX;
    h = t = SIZE;

    for (i = 1; i <= n; i++) {
        scanf("%d", &x);

        while (v[h].i <= i - k) {
            h++;
        }

        if (x < v[h].x) {
            h--;
            v[h].x = x;
            v[h].i = i;
        } else {
            v[t].x = x;
            v[t].i = i;
            t++;
        }

        if (i >= k && v[h].x > s.m) {
            s.m = v[h].x;
            s.b = v[h].i;
        }
    }

    printf("%d %d %d\n", s.b, s.b + k - 1, s.m);

    return 0;
}