Submission #251553

#	Time	Username	Problem	Language	Result	Execution time	Memory
251553		imeimi2000	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	692 ms	79224 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;
typedef long long llong;

int n;
int A[200001];
vector<int> H[200001];
int I[200002];
int D[200001];
int V[200001];

vector<int> child[200001];

void add(int &ord, int p, int l, int r) {
    if (r - l - 1 <= 0) return;
    int i = ++ord;
    child[p].push_back(i);
    I[l] = i;
}

const int L = 18;
int st[200001], ed[200001], dep[200001], par[200001][L];
void dfs(int x, int p) {
    static int ord = 0;
    st[x] = ++ord;
    par[x][0] = p;
    for (int i = 1; i < L; ++i) par[x][i] = par[par[x][i - 1]][i - 1];
    for (int i : child[x]) {
        dfs(i, x);
    }
    ed[x] = ord;
}

vector<pair<int, int>> C[200001];
llong dp[200001], sum[200001];

llong fen[200001];

void update(int i, llong x) {
    while (i <= n) {
        fen[i] += x;
        i += i & -i;
    }
}

llong query(int i) {
    llong ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

void dfs2(int x, int p) {
    for (int i : child[x]) {
        dfs2(i, x);
        sum[x] += dp[i];
    }
    for (auto [y, c] : C[x]) {
        dp[x] = max(dp[x], query(st[y]) + c);
    }
    update(st[x], -dp[x]);
    update(ed[x] + 1, dp[x]);
    dp[x] += sum[x];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        H[A[i]].push_back(i);
    }
    set<int> cut;
    cut.insert(0);
    cut.insert(n + 1);
    int ord = 0;
    D[0] = n;
    I[0] = ++ord;
    for (int h = n; h > 0; --h) {
        for (int i = 0; i < int(H[h].size()); ) {
            int x = H[h][i];
            auto it = cut.lower_bound(x);
            int l = *prev(it), r = *it;
            int p = I[l];
            D[p] = h;
            while (i < int(H[h].size()) && H[h][i] < r) {
                add(ord, p, l, H[h][i]);
                cut.insert(l = H[h][i]);
                V[l] = p;
                ++i;
            }
            add(ord, p, l, r);
        }
    }
    dfs(1, 0);
    int q;
    cin >> q;
    llong sum = 0;
    while (q--) {
        int x, y, c;
        cin >> x >> y >> c;
        sum += c;
        int dn = V[x];
        int up = dn;
        for (int i = L; i--; ) if (D[par[up][i]] < y) up = par[up][i];
        C[up].emplace_back(dn, c);
    }
    dfs2(1, 0);
    printf("%lld\n", sum - dp[1]);
    return 0;
}

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