Submission #1154273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154273		jmuzhen	Po (COCI21_po)	C++20	70 / 70	16 ms	5568 KiB

Main

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

struct UnionFind {
    vector<int> parent, sz;
    // cost: minimum enhancements needed for this contiguous block
    // level: the common “activation” level for this block (the value at which it was raised)
    vector<long long> cost, level;
    long long ans;  // global answer: sum of costs over active blocks

    UnionFind(int n) : parent(n), sz(n, 1), cost(n, 0), level(n, 0), ans(0) {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find(parent[v]);
    }

    // Merge two adjacent blocks a and b.
    // The new block's level becomes min(level[a], level[b]).
    // If the two blocks have the same level, then they share one enhancement,
    // so we subtract 1 from the sum of their costs.
    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;

        // Remove the old blocks’ costs from the global answer.
        ans -= cost[a];
        ans -= cost[b];

        // Union by size.
        if (sz[a] < sz[b])
            swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];

        long long newLevel = min(level[a], level[b]);
        long long newCost;
        if (level[a] == level[b])
            newCost = cost[a] + cost[b] - 1;
        else
            newCost = cost[a] + cost[b];

        level[a] = newLevel;
        cost[a] = newCost;
        ans += cost[a];
    }
};

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

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    // We only “activate” indices with a positive final value.
    vector<bool> active(n, false);
    UnionFind uf(n);

    // Create vector of (value, index) for indices with a[i] > 0.
    vector<pair<long long, int>> nodes;
    for (int i = 0; i < n; i++){
        if(a[i] > 0)
            nodes.push_back({a[i], i});
    }
    // Process in decreasing order.
    sort(nodes.begin(), nodes.end(), [](auto &p1, auto &p2){
        return p1.first > p2.first;
    });

    // Activate indices in descending order.
    for (auto &p : nodes) {
        long long val = p.first;
        int idx = p.second;
        active[idx] = true;
        uf.cost[idx] = 1;   // Activation cost: one enhancement for this index.
        uf.level[idx] = val; // Store the final value at this index.
        uf.ans += 1;        // Increase global answer.

        if (idx - 1 >= 0 && active[idx - 1]) {
            uf.merge(idx, idx - 1);
        }
        if (idx + 1 < n && active[idx + 1]) {
            uf.merge(idx, idx + 1);
        }
    }
    
    cout << uf.ans << "\n";
}

• Subtask 1: 70 / 70