Pagini recente » Felinare | Renovare | Panou | Cod sursa (job #33766) | Cod sursa (job #3208)
Cod sursa(job #3208)
#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] != i) && (heap_to_vector[0] <= n - k)){
for (int j = 1; j < k; ++j) {
heap_elems[j] = vec[heap_to_vector[0] + j];
heap_to_vector[j] = heap_to_vector[0] + j;
vector_to_heap[heap_to_vector[0] + j] = j;
}
build_heap();
i = heap_to_vector[0];
}
}
}
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;
}