Submission #171989

#	Time	Username	Problem	Language	Result	Execution time	Memory
171989		rama_pang	Fireworks (APIO16_fireworks)	C++14	0 / 100	2 ms	504 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

struct Node {
    lint a, b; // y = ax + b, for big x where x >= pq.top()
    priority_queue<lint> pq; // point-slope container

    Node() : a(0), b(0), pq()  {}

    Node& operator+=(Node& o) {
        a += o.a;
        b += o.b;

        if (pq.size() < o.pq.size()) {
            swap(pq, o.pq);
        }

        while (!o.pq.empty()) { // weighted union heuristic
            pq.emplace(o.pq.top());
            o.pq.pop();
        }

        while (a > 1) {
            a--; // ax + b = a(x - 1) + (b + x)
            b += pq.top();
            pq.pop();
        }

        return *this;
    }

    lint solve() {
        while (a > 0) {
            a--;
            b += pq.top();
            pq.pop();
        }
        return b;
    }

};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> p(n + m, -1), c(n + m, 0);
    for (int i = 1; i < n + m; i++) {
        cin >> p[i] >> c[i];
        p[i]--;
    }

    vector<Node> tree(n + m);
    for (int i = n + m - 1; i >= n; i--) {
        tree[i].a = 1;
        tree[i].b = -c[i];
        tree[i].pq.emplace(c[i]); // between slope -1 and 0
        tree[i].pq.emplace(c[i]); // between slope 0 and 1
        tree[p[i]] += tree[i];
    }

    for (int i = n - 1; i > 0; i--) {
        lint top1 = tree[i].pq.top();
        tree[i].pq.pop();
        lint top2 = tree[i].pq.top();
        tree[i].pq.pop();

        tree[i].pq.emplace(top1 + c[i]); // shift slope 1 by c[i]
        tree[i].pq.emplace(top2 + c[i]); // shift slope 0 by c[i]

        tree[i].b -= c[i]; // shift line to right by c[i]
        tree[p[i]] += tree[i];
    }

    cout << tree[0].solve() << "\n";
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45