Submission #726062

#	Time	Username	Problem	Language	Result	Execution time	Memory
726062		piOOE	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	1660 ms	478360 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N_ = 8e5 * 20 * 2 + 1;
int top = 1;

struct Node {
    ll sum = 0, mxp = 0;
    int left = 0, right = 0;
} t[N_];

int create() {
    return top++;
}

void pull(int x) {
    int l = t[x].left, r = t[x].right;
    t[x].sum = t[l].sum + t[r].sum;
    t[x].mxp = max(t[l].mxp, t[l].sum + t[r].mxp);
}

void modify(int x, int lx, int rx, int i, ll d) {
    if (lx == i && rx == i + 1) {
        t[x].sum += d;
        t[x].mxp = max(t[x].sum, 0LL);
        return;
    }

    int mid = (lx + rx) >> 1;

    if (i < mid) {
        if (t[x].left == 0) {
            t[x].left = create();
        }
        modify(t[x].left, lx, mid, i, d);
    } else {
        if (t[x].right == 0) {
            t[x].right = create();
        }
        modify(t[x].right, mid, rx, i, d);
    }

    pull(x);
}

constexpr int N = 2e5 + 1;

vector<int> adj[N], inside[N];

int fa[N], n;

void initFa() {
    iota(fa, fa + n + 1, 0);
    for (int i = 0; i < n; ++i) {
        inside[i] = {i};
    }
}

int leader(int x) {
    while (x != fa[x]) {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}

void unite(int x, int y) {
    x = leader(x), y = leader(y);
    if (x == y) {
        return;
    }

    if (inside[x].size() < inside[y].size()) {
        swap(inside[x], inside[y]);
    }
    inside[x].insert(inside[x].end(), inside[y].begin(), inside[y].end());
    inside[y].clear();

    fa[y] = x;
}

int yy[N], h[N], H[N], C[N], siz[N], root[N];
int m = 0;

pair<ll, ll> getBest(int x, int i) {
    int lx = 0, rx = m;
    ll ans = 0, sum = 0;
    while (lx + 1 < rx) {
        int mid = lx + rx >> 1;
        if (i < mid) {
            ans = max(ans, t[t[x].right].mxp + t[t[x].left].sum + sum);
            rx = mid;
            x = t[x].left;
        } else {
            sum += t[t[x].left].sum;
            lx = mid;
            x = t[x].right;
        }
    }
    sum += t[x].sum;
    ans = max(ans, sum);
    return {ans, sum};
}

void modify(int x, int l, int r, ll d) {
    if (l < m) {
        modify(x, 0, m, l, d);
    }
    if (r < m) {
        modify(x, 0, m, r, -d);
    }
}

void addDP(int x, int i, ll dp) {
    auto [ans, sum] = getBest(x, i);
    ans += dp;
    assert(ans >= sum);
    modify(x, i, i + 1, ans - sum);
}


void upd(int x, int i) {
    addDP(x, i, 0);
}

void dfs(int v) {
    sort(inside[v].begin(), inside[v].end(), [&](int i, int j) {
        return H[i] < H[j];
    });

    vector<int> ours = inside[v];

    siz[v] = inside[v].size();

    for (int to: adj[v]) {
        dfs(to);
        siz[v] += siz[to];
    }

    sort(adj[v].begin(), adj[v].end(), [&](int x, int y) {
        return siz[x] > siz[y];
    });

    if (adj[v].empty()) {
        root[v] = create();
    } else {
        root[v] = root[adj[v][0]];
        unite(v, adj[v][0]);
    }

    auto fuck = [&](int l, int r, ll dp) {
        upd(root[v], r - 1);
        modify(root[v], l, r, dp);
    };

    for (int i = 1; i < adj[v].size(); ++i) {
        int to = adj[v][i];

        sort(inside[to].begin(), inside[to].end(), [&](int x, int y) {
            return H[x] < H[y];
        });

        for (int x = 0; x < inside[to].size(); ++x) {
            int l = x == 0 ? 0 : h[inside[to][x - 1]] + 1;
            int r = h[inside[to][x]] + 1;
            ll dp = getBest(root[to], h[inside[to][x]]).first;
            fuck(l, r, dp);
        }

        unite(v, to);
    }

    for (int i = 0, j = 0; i < ours.size(); i = j) {
        ll sum = 0;
        while (j < ours.size() && H[ours[i]] == H[ours[j]]) {
            sum += C[ours[j]];
            j += 1;
        }
        addDP(root[v], h[ours[i]], sum);
    }
}

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

    cin >> n;

    vector<int> p(n);

    for (int i = 0; i < n; ++i) {
        cin >> p[i] >> H[i] >> C[i];
        p[i] -= 1;
    }

    copy(H, H + n, yy);

    sort(yy, yy + n);
    m = unique(yy, yy + n) - yy;

    for (int i = 0; i < n; ++i) {
        h[i] = lower_bound(yy, yy + m, H[i]) - yy;
    }

    vector<int> used(n);
    initFa();
    int T = 0;

    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            continue;
        }

        int x = i;
        ++T;
        vector<int> now;

        while (!used[x]) {
            now.push_back(x);
            used[x] = T;
            x = p[x];
        }

        if (used[x] == T) {
            int y = p[x];
            while (y != x) {
                unite(x, y);
                y = p[y];
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (leader(i) == i) {
            int x = leader(p[i]);
            if (x == i) {
                adj[n].push_back(i);
//                cout << n << "->" << i << endl;
            } else {
                adj[x].push_back(i);
//                cout << x << "->" << i << endl;
            }
        }
    }

    dfs(n);

    ll ans = getBest(root[n], 0).first;

    ans = accumulate(C, C + n, 0LL) - ans;

    cout << ans << '\n';


    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'std::pair<long long int, long long int> getBest(int, int)':
worst_reporter2.cpp:90:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
worst_reporter2.cpp: In function 'void dfs(int)':
worst_reporter2.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 1; i < adj[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
worst_reporter2.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int x = 0; x < inside[to].size(); ++x) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:174:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (int i = 0, j = 0; i < ours.size(); i = j) {
      |                            ~~^~~~~~~~~~~~~
worst_reporter2.cpp:176:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         while (j < ours.size() && H[ours[i]] == H[ours[j]]) {
      |                ~~^~~~~~~~~~~~~

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