Cod sursa(job #1016840)

Utilizator blasterzMircea Dima blasterz Data 26 octombrie 2013 20:20:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda pq Marime 1.79 kb
#include <cstdio>
#define dim 8192
#define N 500001
char ax[dim];
int pz;
inline void cit(int &x) {
    x = 0;
    while ((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    int neg = 0;
    if (ax[pz] == '-') {
        neg = 1;
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    }
    while (ax[pz] >= '0' && ax[pz] <= '9') {
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    }
    if (neg)
        x = -x;
}

int a[N], H[N], poz[N];
int n, K;
int nh;
inline void swap(int i, int j) {
    int t = H[i]; H[i] = H[j]; H[j] = t;
    poz[H[i]] = i;
    poz[H[j]] = j;
}

inline void upHeap(int i) {
    while (i > 1 && a[ H[i] ] < a[ H[i >> 1] ])
        swap(i, i >> 1), i >>= 1;
}
inline void downHeap(int i) {
    int m = 0;
    while (1) {
        m = i;
        if ((i << 1) <= nh && a[ H[i << 1] ] < a[ H[m] ])
            m = i << 1;
        if (((i << 1) | 1) <= nh && a[ H[(i << 1) | 1] ]< a[ H[m] ] )
            m = (i << 1) | 1;
        if (m != i)
            swap(m, i), i = m;
        else break;
    }
}
int main() {
    freopen ("secventa.in", "r", stdin);
    freopen ("secventa.out", "w", stdout);
    cit(n); cit(K);
    int i, st = 0, dr = 0, res = -0x3f3f3f3f, u, v;
    for (i = 1; i <= n; ++i)
        cit(a[i]);
    
    nh = K - 1;
    for (i = 1; i <= nh; ++i)
        H[i] = i, poz[i] = i;
    for (i = nh / 2; i >= 1; --i)
        downHeap(i);
    for (i = K; i <= n; ++i) {
        H[++nh] = i;
        poz[i] = nh;
        upHeap(nh);
        if (a[ H[1] ] > res)
            res = a[ H[1] ], st = i - K + 1, dr = i;
        int u = poz[i - K + 1];
        swap(nh--, u);
        downHeap(u);
    }

    printf ("%d %d %d\n", st, dr, res);

}