1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int s, e;                 // interval [s, e]
    long long w;              // weight (aesthetic value)
    vector<int> child;        // children in laminar tree
    priority_queue<long long> diffs; // descending difference sequence of F_u
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; if (!(cin >> N)) return 0;
    vector<Node> a(N + 1);
    const int ROOT = 0;
    a[ROOT].s = -1; a[ROOT].e = INT_MAX; a[ROOT].w = 0;

    for (int i = 1; i <= N; ++i) {
        int S, E; long long V; cin >> S >> E >> V;
        a[i].s = S; a[i].e = E; a[i].w = V;
    }

    // Build laminar tree: sort by (s asc, e desc), stack to assign parent
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int x, int y){
        if (a[x].s != a[y].s) return a[x].s < a[y].s;
        return a[x].e > a[y].e; // longer first when start equal
    });

    vector<int> st; st.reserve(N + 1);
    st.push_back(ROOT);
    for (int id : ord) {
        while (!st.empty() && a[st.back()].e <= a[id].s) st.pop_back();
        int p = st.empty() ? ROOT : st.back();
        a[p].child.push_back(id);
        st.push_back(id);
    }

    // Postorder (iterative) to process children before parent
    vector<int> post; post.reserve(N + 1);
    vector<pair<int,int>> dfs; dfs.reserve(N + 1);
    dfs.push_back({ROOT, 0});
    while (!dfs.empty()) {
        auto [u, t] = dfs.back(); dfs.pop_back();
        if (t == 0) {
            dfs.push_back({u, 1});
            for (int v : a[u].child) dfs.push_back({v, 0});
        } else post.push_back(u);
    }

    auto merge_into = [&](int u, int v) {
        // Pointwise add child v into u on difference sequences via zipped addition.
        // Keep u as the larger container (small-to-large) to bound complexity.
        if (a[v].diffs.size() > a[u].diffs.size()) swap(a[u].diffs, a[v].diffs);
        vector<long long> buf; buf.reserve(a[v].diffs.size());
        while (!a[v].diffs.empty()) {
            long long bv = a[v].diffs.top(); a[v].diffs.pop();
            long long au = 0;
            if (!a[u].diffs.empty()) { au = a[u].diffs.top(); a[u].diffs.pop(); }
            buf.push_back(au + bv);
        }
        for (long long x : buf) a[u].diffs.push(x);
    };

    for (int u : post) {
        // 1) Merge all children into u (S = sum of children)
        for (int v : a[u].child) merge_into(u, v);
        // 2) Insert node weight (F = max(S, w + S shifted)) => push w into diffs
        a[u].diffs.push(a[u].w);
    }

    // Root answers: prefix sums of top k differences
    vector<long long> ans(N + 1, 0);
    long long acc = 0;
    for (int k = 1; k <= N; ++k) {
        if (!a[ROOT].diffs.empty()) { acc += a[ROOT].diffs.top(); a[ROOT].diffs.pop(); }
        ans[k] = acc;
    }

    for (int k = 1; k <= N; ++k) {
        if (k > 1) cout << ' ';
        cout << ans[k];
    }
    cout << '\n';
    return 0;
}