제출 #373722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373722		KoD	Fireworks (APIO16_fireworks)	C++17	100 / 100	1596 ms	104044 KiB

fireworks

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;
using ll = long long;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);        
    }
};

struct HeapNode;
using Heap = std::unique_ptr<HeapNode>;

struct HeapNode {
    ll value, lazy;
    Heap left, right;
    HeapNode(const ll value): value(value), lazy(0), left(), right() { }
};

void flush(Heap &heap) {
    heap -> value += heap -> lazy;
    if (heap -> left) heap -> left -> lazy += heap -> lazy;
    if (heap -> right) heap -> right -> lazy += heap -> lazy;
    heap -> lazy = 0;
}

Heap merge(Heap left, Heap right) {
    if (!left) return right;
    if (!right) return left;
    flush(left);
    flush(right);
    if (left -> value < right -> value) {
        std::swap(left, right);
    }
    left -> right = merge(std::move(left -> right), std::move(right));
    std::swap(left -> left, left -> right);
    return left;
}

void push(Heap &heap, const ll value) {
    heap = merge(std::move(heap), std::make_unique<HeapNode>(value));
}

ll top(Heap &heap) {
    flush(heap);
    return heap -> value;
}

ll pop(Heap &heap) {
    const auto ret = top(heap);
    heap = merge(std::move(heap -> left), std::move(heap -> right));
    return ret;
}

void add(Heap &heap, const ll value) {
    heap -> lazy += value;
}

struct SlopeTrick {
    ll last_slope, last_y;
    Heap changes;

    SlopeTrick(): last_slope(), last_y(), changes() { 
        push(changes, 0);
    }
    
    void absorb(SlopeTrick &&other) {
        const auto x1 = top(changes);
        const auto x2 = top(other.changes);
        last_y += other.last_y + (x1 < x2 ? last_slope * (x2 - x1) : other.last_slope * (x1 - x2));
        last_slope += other.last_slope;
        changes = merge(std::move(changes), std::move(other.changes));
    }

    bool pop_last() {
        const auto x1 = pop(changes);
        if (!changes) return false;
        const auto x2 = top(changes);
        last_slope -= 1;
        last_y += last_slope * (x2 - x1);
        return true;
    }
};

int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<Vec<std::pair<int, int>>> children(N + M);
    for (int i = 1; i < N + M; ++i) {
        int p, c;
        std::cin >> p >> c;
        p -= 1;
        children[p].emplace_back(i, c);
    }
    Vec<SlopeTrick> data(N);
    RecLambda([&](auto dfs, const int u) -> void {
        for (const auto [v, c]: children[u]) {
            if (v >= N) {
                SlopeTrick trick;
                trick.last_slope = 1;
                push(trick.changes, c);
                push(trick.changes, c);
                data[u].absorb(std::move(trick));
            }
            else {
                dfs(v);
                while (data[v].last_slope > 1) {
                    data[v].pop_last();
                }
                const auto x1 = pop(data[v].changes);
                const auto x2 = pop(data[v].changes);
                push(data[v].changes, x2 + c);
                push(data[v].changes, x1 + c);
                data[u].absorb(std::move(data[v]));
            }
        }
    })(0);
    ll ans = data[0].last_y;
    while (data[0].pop_last()) {
        ans = std::min(ans, data[0].last_y);
    }
    std::cout << ans << '\n';
    return 0;    
}

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