Cod sursă (job #145100)

#include <iostream>
#include <fstream>
using namespace std;

// adaug o inaltime
// sterg cele mai mari 1/2 din inaltimi
// cresc toate inaltimile cu 1

// adaug o inaltime
// sterg inaltime maxima
// cresc toate inaltimile cu 1

ifstream fi ("lalele.in");
ofstream fo ("lalele.out");

const int dimN = 5000003;

int N, NH, time = 1;

struct Node {
    int initialVal;
    int t0;
    int val() { return time - t0 + initialVal; }
    bool priorTo(Node n) { return this->val() > n.val(); }
};

Node H[dimN];

void upheap(int n) {
    int t = n >> 1;
    while (t && H[n].priorTo(H[t])) {
        swap(H[n], H[t]);
        n = t;
        t = n >> 1;
    }
}

void downheap(int n) {
    int f = n << 1;
    if (f+1 <= NH && H[f+1].priorTo(H[f])) f++;
    while (f <= NH && H[f].priorTo(H[n])) {
        swap(H[n], H[f]);
        n = f;
        f = n << 1;
        if (f+1 <= NH && H[f+1].priorTo(H[f])) f++;
    }
}

void remove_heap_top() {
    H[1] = H[NH];
    NH--;
    downheap(1);
}

void add_element(int val) {
    H[++NH].initialVal = val;
    H[NH].t0 = time;
    upheap(NH);
}

void update_tot(int val) {
    time += val;
}

void remove_jumatate() {

    int middle = NH / 2 + 1;
    int lastVal;

    for (int i = NH; i >= middle; i--) {
        lastVal = H[1].val();
        remove_heap_top();
    }
    NH = middle - 1;
    fo << lastVal << '\n';
    //cout << "LastVal:" << lastVal << '\n';
    return;
}

int main()
{
    fi >> N;
    int daysLeft = N, d, x;

    while (daysLeft) {

        fi >> d >> x;
        daysLeft -= d;

        for (int i = 1; i <= d; i++) {
            if (x > 0) {
                add_element(x);
            } else if (x == 0) {
                remove_jumatate();
            }
            update_tot(1);

            /*
            cout << "H:";
            for (int i = 1; i <= NH; i++)
                cout << H[i].val() << ' ';
            cout << "\n";
            */
        }


    }
    return 0;
}