Submission #1239875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239875		Double_Slash	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	79 / 100	394 ms	105132 KiB

worst_reporter2

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int INF = 1e9;
int n, a[200001], h[200001], c[200001], sz;
struct Node {
    ll sum;
    int lc, rc;
} mem[1 << 23];
vector<int> adj[200001];

void upd(int &n, int i, int v, int l, int r) {
    if (not n) n = ++sz;
    mem[n].sum += v;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (i <= m) upd(mem[n].lc, i, v, l, m);
    else upd(mem[n].rc, i, v, m + 1, r);
}

void erase(int &n, int i, int &v, int l, int r) {
    // cerr << l << ' ' << r << ' ' << mem[n].sum << ' ' << v << endl;
    if (l > i or not v) return;
    if (r <= i and mem[n].sum <= v) {
        v -= mem[n].sum;
        n = 0;
    }
    if (not n) return;
    if (l == r) {
        mem[n].sum -= v;
        v = 0;
        return;
    }
    int m = (l + r) >> 1;
    erase(mem[n].rc, i, v, m + 1, r);
    erase(mem[n].lc, i, v, l, m);
    mem[n].sum = mem[mem[n].lc].sum + mem[mem[n].rc].sum;
}

int merge(int a, int b) {
    if (not a or not b) return max(a, b);
    mem[a].sum += mem[b].sum;
    mem[a].lc = merge(mem[a].lc, mem[b].lc);
    mem[a].rc = merge(mem[a].rc, mem[b].rc);
    return a;
}

int dfs(int i) {
    int root = 0;
    for (int j: adj[i]) root = merge(root, dfs(j));
    upd(root, h[i], c[i], 1, INF);
    erase(root, h[i] - 1, c[i], 1, INF);
    return root;
}

int main() {
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> h[i] >> c[i];
        if (i > 1) adj[a[i]].emplace_back(i);
        sum += c[i];
    }
    cout << sum - mem[dfs(1)].sum;
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21