oj.uz

Submission #172000

# Submission time Handle Problem Language Result Execution time Memory
172000 2019-12-30T18:45:16 Z rama_pang Fireworks (APIO16_fireworks) C++14
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

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

    Node() : a(0), b(0) {
        slope = new priority_queue<lint>();
    }

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

        // if (slope->size() < o.slope->size()) {
        //     swap(slope, o.slope);
        // }

        while (!o.slope->empty()) {
            slope->emplace(o.slope->top());
            o.slope->pop();
        }
        
        while (a > 1) {
            a--; // ax + b = a(x - 1) + (b + x)
            b += slope->top();
            slope->pop();
        }

        return *this;
    }

    lint solve() {
        while (a > 0) {
            a--;
            b += slope->top();
            slope->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].slope->emplace(c[i]); // between slope -1 and 0
        tree[i].slope->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].slope->top();
        tree[i].slope->pop();
        lint top2 = tree[i].slope->top();
        tree[i].slope->pop();

        tree[i].slope->emplace(top1 + c[i]); // shift slope 1 by c[i]
        tree[i].slope->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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -