Cod sursa(job #3213)

Utilizator demonuTeodor Stoenescu demonu Data 21 decembrie 2006 23:04:33
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <stdio.h>

const char *fin = "secventa.in";
const char *fout = "secventa.out";

short vec[500030], heap_elems[500030];
int n = 0, k = 0, p = 0, bmax = -30000;
int heap_to_vector[500030], vector_to_heap[500030];

#define parent(x) ((x - 1) / 2)
#define left(x) (2 * (x) + 1)
#define right(x) (2 * (x) + 2)

inline void swap(const int a, const int b) {
    vector_to_heap[heap_to_vector[a]] = b;
    vector_to_heap[heap_to_vector[b]] = a;
    heap_elems[a] ^= heap_elems[b] ^= heap_elems[a] ^= heap_elems[b];
    heap_to_vector[a] ^= heap_to_vector[b] ^= heap_to_vector[a] ^= heap_to_vector[b];
}

void sift(int elem) {
    int kk = -1;
    if (left(elem) < k) {
        kk = left(elem);
        if ((right(elem) < k) && (heap_elems[right(elem)] < heap_elems[left(elem)])) {
            kk = right(elem);
        }
        if (heap_elems[elem] < heap_elems[kk]) {
            kk = -1;
        }
    }

    while (kk != -1) {
        swap(elem, kk);
        elem = kk;
        kk = -1;
        if (left(elem) < k) {
            kk = left(elem);
            if ((right(elem) < k) && (heap_elems[right(elem)] < heap_elems[left(elem)])) {
                kk = right(elem);
            }
            if (heap_elems[elem] < heap_elems[kk]) {
                kk = -1;
            }
        }
    }
}

void percolate(int elem) {
    while ((elem) && (heap_elems[elem] < heap_elems[parent(elem)])) {
        swap(elem, parent(elem));
        elem = parent(elem);
    }
}

void build_heap() {
    for(int i = parent(k - 1); i >= 0; --i) {
        sift(i);
    }
}

void solve() {
    for (int i = 0; i < k; ++i) {
        heap_elems[i] = vec[i];
        heap_to_vector[i] = i;
        vector_to_heap[i] = i;
    }

    build_heap();

    if (heap_elems[0] > bmax) {
        bmax = heap_elems[0];
        p = 0;
    }

    for (int i = 1; i <= n - k; ++i) {
        heap_elems[vector_to_heap[i - 1]] = vec[k + i - 1];
        vector_to_heap[k + i - 1] = vector_to_heap[i - 1];
        heap_to_vector[vector_to_heap[k + i - 1]] = k + i - 1;

        if (vec[i - 1] < vec[k + i - 1]) {
            sift(vector_to_heap[k + i - 1]);
        } else if (vec[i - 1] > vec[k + i - 1]) {
            percolate(vector_to_heap[k + i - 1]);
        }

        if (heap_elems[0] > bmax) {
            bmax = heap_elems[0];
            p = i;
        } else if ((heap_to_vector[0] == k + i - 1) && (k + i - 1 <= n - k)){
            for (int j = 1; j < k; ++j) {
                heap_elems[j] = vec[k + i - 1 + j];
                heap_to_vector[j] = k + i - 1 + j;
                vector_to_heap[k + i - 1 + j] = j;
            }
            build_heap();
            i += k - 1;
        }
    }
}

int main() {
    FILE *f = fopen(fin, "rt");
    fscanf(f, "%d %d", &n, &k);
    for(int i = 0; i < n; ++i) {
        fscanf(f, "%d", &vec[i]);
    }
    fclose(f);

    solve();

    f = fopen(fout, "wt");
    fprintf(f, "%d %d %d", p + 1, p + k, bmax);
    fclose(f);
    return 0;
}