Submission #1197507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197507		LucaIlie	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	1596 ms	37488 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

struct star {
    int i, j, c;
};

const int MAX_N = 2e5;
const int MAX_M = 2e5;
int n;
int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2], cost[MAX_N + 2];
long long dp[MAX_N + 2], sum[MAX_N + 2];
star stars[MAX_M];
vector<int> starsByColumn[MAX_N + 2];
vector<int> starsByFinish[MAX_N + 2];

vector<int> path;
void dfs(int v) {
    if (v == 0)
        return;

    path.push_back(v);

    for (int i: starsByColumn[v]) {
        int l = -1, r = path.size() - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (h[path[mid]] < stars[i].j)
                r = mid;
            else
                l = mid;
        }
        /* printf("STAR %d %d\n", i, path[r]); */
        starsByFinish[path[r]].push_back(i);
    }

    /* printf("%d %d %d\n", v, leftSon[v], rightSon[v]); */
    dfs(leftSon[v]);
    dfs(rightSon[v]);

    path.pop_back();
}

void calcCost(int v) {
    if (v == 0)
        return;

    calcCost(leftSon[v]);
    calcCost(rightSon[v]);

    sum[v] = dp[leftSon[v]] + dp[rightSon[v]];
    dp[v] = sum[v];

    for (int i: starsByFinish[v]) {
        int u = stars[i].i;
        long long add = 0;
        while (u != v) {
            add += sum[u] - dp[u];
            u = parent[u];
        }
        add += sum[v];
        dp[v] = max(dp[v], add + stars[i].c);
    }

    /* printf("%d %lld %lld\n", v, dp[v], sum[v]); */
}

int main() {
    int m;
    long long total = 0;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> stars[i].i >> stars[i].j >> stars[i].c;
        total += stars[i].c;
    }

    h[n + 1] = n + 1;
    vector<int> stack;
    for (int i = 1; i <= n + 1; i++) {
        vector<int> path;
        while (!stack.empty() && h[i] >= h[stack.back()]) {
            path.push_back(stack.back());
            stack.pop_back();
        }
        path.push_back(i);
        stack.push_back(i);

        for (int j = 0; j < (int)path.size() - 1; j++)
            parent[path[j]] = path[j + 1];
    }

    for (int v = 1; v <= n; v++) {
        if (v < parent[v])
            leftSon[parent[v]] = v;
        else
            rightSon[parent[v]] = v;
    }

    for (int i = 0; i < m; i++)
        starsByColumn[stars[i].i].push_back(i);

    dfs(n + 1);
    calcCost(n + 1);

    cout << total - dp[n + 1] << "\n";
}

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