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:
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 here:
```cpp #include <iostream> #include <vector> #include <algorithm> #include <functional> using std::cout; using std::endl; using std::vector; using std::pair; using Pos = pair<int, int>; 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; } } ```