Cod sursa(job #2143046)

Utilizator 24601Dan Ban 24601 Data 25 februarie 2018 15:21:16
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.84 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];

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 = 0;

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

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

        while (t > h && v[t - 1].x > x) {
            cmin = v[t - 1].i;
            t--;
        }

        v[t].x = x;
        v[t].i = i;
        t++;

        if (v[h].x > s.m) {
            s.m = v[h].x;
            s.b = cmin < v[h].i ? cmin : v[h].i;
        }
    }

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

    return 0;
}