Submission #1197524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197524		LucaIlie	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	341 ms	48068 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

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

struct AIB {
    vector<long long> aib;

    void init(int n) {
        aib.resize(n);
    }

    void update(int i, long long x) {
        while (i < (int)aib.size()) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    long long query(int i) {
        long long s = 0;
        while (i > 0) {
            s += aib[i];
            i -= (i & -i);
        }
        return s;
    }
};

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];
int timeIn[MAX_N + 2], timeOut[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];
AIB aib;

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

    path.push_back(v);
    timeIn[v] = ++timee;

    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;
        }
        starsByFinish[path[r]].push_back(i);
    }

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

    path.pop_back();
    timeOut[v] = ++timee;
}

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 = sum[v] + aib.query(timeIn[u]) - aib.query(timeIn[v]);
        dp[v] = max(dp[v], add + stars[i].c);
    }
    sum[v] -= dp[v];

    aib.update(timeIn[v], sum[v]);
    aib.update(timeOut[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);
    aib.init(timee);
    calcCost(n + 1);

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

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