Submission #518945

#	Time	Username	Problem	Language	Result	Execution time	Memory
518945		ParsaAlizadeh	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	537 ms	35908 KiB

worst_reporter2

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

typedef long long ll;
typedef pair<int,int> pii;

#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second
#define lc (id<<1)
#define rc (lc|1)

void assume(int expr) {
    if (!expr) __builtin_unreachable();
}

constexpr int N = 2e5 + 10;

int n, L[N], R[N];
ll H[N], C[N], dp[N];
vector<int> adj[N];

namespace Seg {
    ll seg[N<<2];
    void modify(int id, int l, int r, int ind, ll c) {
        if (r-l == 1) {
            seg[id] = c;
            return;
        }
        int mid = (l+r) >> 1;
        if (ind < mid) modify(lc, l, mid, ind, c);
        else modify(rc, mid, r, ind, c);
        seg[id] = seg[lc] + seg[rc];
    }
    ll get(int id, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql)
            return 0;
        if (ql <= l && r <= qr)
            return seg[id];
        int mid = (l+r) >> 1;
        return get(lc, l, mid, ql, qr) + get(rc, mid, r, ql, qr);
    }
}

namespace JadSeg {
    int seg[N<<2];
    void build(int id, int l, int r) {
        if (r-l == 1) {
            seg[id] = l;
            return;
        }
        int mid = (l+r) >> 1;
        build(lc, l, mid); build(rc, mid, r);
        seg[id] = max(seg[lc], seg[rc]);
    }
    void modify(int id, int l, int r, int ind, int c) {
        if (r-l == 1) {
            seg[id] = c;
            return;
        }
        int mid = (l+r) >> 1;
        if (ind < mid)
            modify(lc, l, mid, ind, c);
        else
            modify(rc, mid, r, ind, c);
        seg[id] = max(seg[lc], seg[rc]);
    }
    int get(int id, int l, int r, int ind) {
        if (l >= ind || seg[id] <= ind)
            return -1;
        if (r-l == 1)
            return l;
        int mid = (l+r) >> 1;
        auto res = get(rc, mid, r, ind);
        if (res != -1)
            return res;
        return get(lc, l, mid, ind);
    }
}

void dfs(int u) {
    static int timer = 0;
    L[u] = timer++;
    for (int v : adj[u])
        dfs(v);
    R[u] = timer;
}

void ignre(int i, ll c) {
    // cout << "ignore " << i << ' ' <<c << endl;
    int jad = JadSeg::get(1, 0, n, i);
    if (jad == -1)
        return;
    ll val = Seg::get(1, 0, n, jad, jad+1);
    // cout << "@ " << jad << ' ' << val << endl;
    val -= c;
    if (val >= 0) {
        Seg::modify(1, 0, n, jad, val);
        return;
    }
    Seg::modify(1, 0, n, jad, 0);
    JadSeg::modify(1, 0, n, jad, jad);
    return ignre(jad, -val);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int par;
        cin >> par >> H[i] >> C[i];
        if (i > 1)
            adj[par].push_back(i);
    }
    dfs(1);
    vector<pair<ll,int>> Q;
    Q.reserve(n);
    for (int i = 1; i <= n; i++) {
        Q.emplace_back(H[i], i);
    }
    sort(all(Q), greater<>());
    for (int qi = 0; qi < Q.size(); qi++) {
        int i = Q[qi].snd;
        dp[i] = Seg::get(1, 0, n, L[i], R[i]) + C[i];
        // cout << "add " << L[i] << ' ' << C[i] << endl;
        Seg::modify(1, 0, n, L[i], C[i]);
        JadSeg::modify(1, 0, n, L[i], R[i]);
        ignre(L[i], C[i]);
    }
    ll sm = 0, ans = Seg::get(1, 0, n, 0, n);
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
        sm += C[i];
    }
    // cout << sm << ' ' << ans << endl;
    cout << sm - ans << '\n';
    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:123:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int qi = 0; qi < Q.size(); qi++) {
      |                      ~~~^~~~~~~~~~

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