solution for mountain time

mountain_time.md

first editorial that i can be informal in hooray

anyway the editorial is for this problem it's kinda misleading- they say that the prominence is h_min, when it's really the elevation - h_min

but anyways, this is a dsu problem, if dsu was awful and something you wanted to rage at every night (the 2d aspect doesn't make it any better)
i'll assume you know enough about dsu to not die on a simple problem about it

so you add the squares in one at a time from highest to lowest and link them to any previously added squares with some standard dsu stuff
but because the writers were sadistic you need to keep the tallest mountain in each dsu component (if there's multiple you need to keep all of them)

then when you link two components (i'll call them A and B for simplicity) with some square of elevation e, you compare the highest mountains in each component
there's 3 cases for this comparison:

1. they're equal, in which case you just merge the mountains, standard carp
2. the tallest mountains in A are taller than the ones in B, in which case the h_min of the mountains in B are e
   this is because the current square is the tallest square that can link the squares from B to A (the ones with the strictly higher mountains)- note that we can say this only because we add the squares from the highest to lowest
3. just reverse case of 2, where the ones in B are taller than the ones in A if you can't figure out this by your own you're high

of course you need to still do the standard dsu stuff as mentioned above or else this thing'll be slow as heck

there's a separate case for the highest mountains because they'll never hit case 2 or 3, so we just manually set the prominence of them to their current elevation

code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using std::cout;
using std::endl;
using std::vector;
using std::pair;
using Pos = std::pair<int, int>;

/**
 * https://csacademy.com/contest/archive/task/mountain-time/statement/
 * (input ommitted due to length)
 */
int main() {
    int row_num;
    int col_num;
    std::cin >> row_num >> col_num;
    vector<pair<int, Pos>> mountains;
    int highest = INT32_MIN;
    for (int r = 0; r < row_num; r++) {
        for (int c = 0; c < col_num; c++) {
            int elev;
            std::cin >> elev;
            highest = std::max(highest, elev);
            mountains.push_back({elev, {r, c}});
        }
    }

    vector<vector<Pos>> parent(row_num, vector<Pos>(col_num));
    vector<vector<int>> size(row_num, vector<int>(col_num, 1));
    vector<vector<int>> prominence(row_num, vector<int>(col_num));
    vector<vector<bool>> processed(row_num, vector<bool>(col_num));
    vector<vector<pair<int, vector<Pos>>>> tallest(
        row_num, vector<pair<int, vector<Pos>>>(col_num)
    );
    for (int r = 0; r < row_num; r++) {
        for (int c = 0; c < col_num; c++) {
            tallest[r][c] = {mountains[r * col_num + c].first, {{r, c}}};
            parent[r][c] = {r, c};
            prominence[r][c] = mountains[r * col_num + c].first;
        }
    }

    // made these lambdas because i hate globals that much
    std::function<Pos(const Pos& p)> get_ultimate = [&] (const Pos& p) -> Pos {
        if (parent[p.first][p.second] == p) {
            return p;
        } else {
            return parent[p.first][p.second] = get_ultimate(parent[p.first][p.second]);
        }
    };
    int curr_elev;
    auto link = [&] (Pos m1, Pos m2) -> void {
        m1 = get_ultimate(m1);
        m2 = get_ultimate(m2);
        if (m1 == m2) {
            return;
        }
        if (size[m1.first][m1.second] < size[m2.first][m2.second]) {
            std::swap(m1, m2);  // make m1's size >= m2's size
        }
        pair<int, vector<Pos>>& t1 = tallest[m1.first][m1.second];
        pair<int, vector<Pos>>& t2 = tallest[m2.first][m2.second];
        if (t1.first > t2.first) {
            for (const Pos& p : t2.second) {
                prominence[p.first][p.second] = t2.first - curr_elev;
            }
        } else if (t1.first < t2.first) {
            for (const Pos& p : t1.second) {
                prominence[p.first][p.second] = t1.first - curr_elev;
            }
            t1 = t2;
        } else {
            t1.second.insert(t1.second.end(), t2.second.begin(), t2.second.end());
        }
        // this part is just standard DSU
        parent[m2.first][m2.second] = m1;
        size[m1.first][m1.second] += size[m2.first][m2.second];
    };

    std::sort(
        mountains.begin(), mountains.end(),
        std::greater<pair<int, Pos>>()
    );
    for (const auto& [elev, p] : mountains) {
        processed[p.first][p.second] = true;
        if (elev == highest) {
            prominence[p.first][p.second] = elev;
            continue;
        }
        curr_elev = elev;
        if (p.first > 0 && processed[p.first - 1][p.second]) {
            link(p, {p.first - 1, p.second});
        }
        if (p.second > 0 && processed[p.first][p.second - 1]) {
            link(p, {p.first, p.second - 1});
        }
        if (p.first < row_num - 1 && processed[p.first + 1][p.second]) {
            link(p, {p.first + 1, p.second});
        }
        if (p.second < col_num - 1 && processed[p.first][p.second + 1]) {
            link(p, {p.first, p.second + 1});
        }
    }
    for (int r = 0; r < row_num; r++) {
        for (int c = 0; c < col_num - 1; c++) {
            cout << prominence[r][c] << ' ';
        }
        cout << prominence[r][col_num - 1] << endl;
    }
}