# weekly-contest-212

## A

### Statement

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 `n` 个），每次一个。

``````输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"

'c' 按字母顺序排列比 'b' 大，所以答案是 'c'
``````

``````输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"

• `releaseTimes.length == n`
• `keysPressed.length == n`
• `2 <= n <= 1000`
• `1 <= releaseTimes[i] <= 109`
• `releaseTimes[i] < releaseTimes[i+1]`
• `keysPressed` 仅由小写英文字母组成

• Difficulty: Easy
• Tag: `Array` `String`

A newly designed keypad was tested, where a tester pressed a sequence of `n` keys, one at a time.

You are given a string `keysPressed` of length `n`, where `keysPressed[i]` was the `ith` key pressed in the testing sequence, and a sorted list `releaseTimes`, where `releaseTimes[i]` was the time the `ith` key was released. Both arrays are 0-indexed. The `0th` key was pressed at the time `0`, and every subsequent key was pressed at the exact time the previous key was released.

The tester wants to know the key of the keypress that had the longest duration. The `ith` keypress had a duration of `releaseTimes[i] - releaseTimes[i - 1]`, and the `0th` keypress had a duration of `releaseTimes[0]`.

Note that the same key could have been pressed multiple times during the test, and these multiple presses of the same key may not have had the same duration.

Return the key of the keypress that had the longest duration. If there are multiple such keypresses, return the lexicographically largest key of the keypresses.

Example 1:

``````Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"
Output: "c"
Explanation: The keypresses were as follows:
Keypress for 'c' had a duration of 9 (pressed at time 0 and released at time 9).
Keypress for 'b' had a duration of 29 - 9 = 20 (pressed at time 9 right after the release of the previous character and released at time 29).
Keypress for 'c' had a duration of 49 - 29 = 20 (pressed at time 29 right after the release of the previous character and released at time 49).
Keypress for 'd' had a duration of 50 - 49 = 1 (pressed at time 49 right after the release of the previous character and released at time 50).
The longest of these was the keypress for 'b' and the second keypress for 'c', both with duration 20.
'c' is lexicographically larger than 'b', so the answer is 'c'.
``````

Example 2:

``````Input: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
Output: "a"
Explanation: The keypresses were as follows:
Keypress for 's' had a duration of 12.
Keypress for 'p' had a duration of 23 - 12 = 11.
Keypress for 'u' had a duration of 36 - 23 = 13.
Keypress for 'd' had a duration of 46 - 36 = 10.
Keypress for 'a' had a duration of 62 - 46 = 16.
The longest of these was the keypress for 'a' with duration 16.``````

Constraints:

• `releaseTimes.length == n`
• `keysPressed.length == n`
• `2 <= n <= 1000`
• `1 <= releaseTimes[i] <= 109`
• `releaseTimes[i] < releaseTimes[i+1]`
• `keysPressed` contains only lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

class Solution {
public:
char slowestKey(vector<int> &releaseTimes, string keysPressed) {
n = releaseTimes.size();
vector<int> vec(220, 0);
int pre = 0;
for (int i = 0; i < n; ++i) {
int t = releaseTimes[i] - pre;
int ch = keysPressed[i];
chmax(vec[ch], t);
pre = releaseTimes[i];
}
int Max = 0;
char ch = 'z';
for (int i = 'z'; i >= 'a'; --i) {
if (vec[i] > Max) {
Max = vec[i];
ch = i;
}
}
return ch;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• Difficulty: Medium
• Tag: `数组` `排序`

``````1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9``````

``1, 1, 2, 5, 7``

``````输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]

``````输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]

``````

• `n == nums.length`
• `m == l.length`
• `m == r.length`
• `2 <= n <= 500`
• `1 <= m <= 500`
• `0 <= l[i] < r[i] < n`
• `-105 <= nums[i] <= 105`

A sequence of numbers is called arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence `s` is arithmetic if and only if `s[i+1] - s[i] == s[1] - s[0] `for all valid `i`.

For example, these are arithmetic sequences:

``````1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9``````

The following sequence is not arithmetic:

``1, 1, 2, 5, 7``

You are given an array of `n` integers, `nums`, and two arrays of `m` integers each, `l` and `r`, representing the `m` range queries, where the `ith` query is the range `[l[i], r[i]]`. All the arrays are 0-indexed.

Return a list of `boolean` elements `answer`, where `answer[i]` is `true` if the subarray `nums[l[i]], nums[l[i]+1], … , nums[r[i]]` can be rearranged to form an arithmetic sequence, and `false` otherwise.

Example 1:

``````Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
Output: [true,false,true]
Explanation:
In the 0th query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.
In the 1st query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.
In the 2nd query, the subarray is [5,9,3,7]. This can be rearranged as [3,5,7,9], which is an arithmetic sequence.``````

Example 2:

``````Input: nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
Output: [false,true,false,false,true,true]
``````

Constraints:

• `n == nums.length`
• `m == l.length`
• `m == r.length`
• `2 <= n <= 500`
• `1 <= m <= 500`
• `0 <= l[i] < r[i] < n`
• `-105 <= nums[i] <= 105`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1& x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1& x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1& x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T& arg, Ts&... args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t>& arg, const A&... args) {
for (auto& v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T& arg, const Ts&... args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T& arg, const Ts&... args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t>& arg, const A&... args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n, q;

class Solution {
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
n = nums.size();
q = l.size();
vector<bool> res;
for (int i = 0; i < q; ++i) {
int _l = l[i], _r = r[i];
vector<int> vec;
for (int j = _l; j <= _r; ++j) vec.push_back(nums[j]);
sort(all(vec));
if (SZ(vec) == 1)
res.push_back(true);
else {
int gap = vec[1] - vec[0];
bool ok = true;
for (int i = 2; i < SZ(vec); ++i) {
if (vec[i] - vec[i - 1] != gap) {
ok = 0;
break;
}
}
res.push_back(ok);
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• Difficulty: Medium
• Tag: `深度优先搜索` `广度优先搜索` `并查集` `数组` `二分查找` `矩阵` `堆（优先队列）`

``````输入：heights = [[1,2,2],[3,8,2],[5,3,5]]

``````

``````输入：heights = [[1,2,3],[3,8,4],[5,3,5]]

``````

``````输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]

``````

• `rows == heights.length`
• `columns == heights[i].length`
• `1 <= rows, columns <= 100`
• `1 <= heights[i][j] <= 106`

• Link: Path With Minimum Effort
• Difficulty: Medium
• Tag: `Depth-First Search` `Breadth-First Search` `Union Find` `Array` `Binary Search` `Matrix` `Heap (Priority Queue)`

You are a hiker preparing for an upcoming hike. You are given `heights`, a 2D array of size `rows x columns`, where `heights[row][col]` represents the height of cell `(row, col)`. You are situated in the top-left cell, `(0, 0)`, and you hope to travel to the bottom-right cell, `(rows-1, columns-1)` (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

``````
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
``````

Example 2:

``````
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
``````

Example 3:

``````
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.
``````

Constraints:

• `rows == heights.length`
• `columns == heights[i].length`
• `1 <= rows, columns <= 100`
• `1 <= heights[i][j] <= 106`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e2 + 10;
int n, m;
vector<vector<int>> heights;
int vis[N][N];

int Move[][2] = {-1, 0, 1, 0, 0, 1, 0, -1};

bool valid(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m)
return false;
return true;
}

bool ok(int xx) {
memset(vis, 0, sizeof vis);
queue<pII> que;
que.push(pII(0, 0));
while (!que.empty()) {
pII front = que.front();
que.pop();
int x = front.fi;
int y = front.se;
if (x == n - 1 && y == m - 1)
return true;
for (int i = 0; i < 4; ++i) {
int _x = x + Move[i][0];
int _y = y + Move[i][1];
if (valid(_x, _y) && vis[_x][_y] == 0 && abs(heights[_x][_y] - heights[x][y]) <= xx) {
que.push(pII(_x, _y));
vis[_x][_y] = 1;
}
}
}
return false;
}

class Solution {
public:
int minimumEffortPath(vector<vector<int>> &_heights) {
heights = _heights;
n = heights.size();
m = heights[0].size();
int l = 0, r = 1e6, res = 1e6;
while (r - l >= 0) {
int mid = (l + r) >> 1;
if (ok(mid)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Hard
• Tag: `贪心` `并查集` `图` `拓扑排序` `数组` `矩阵`

• 秩是从 1 开始的一个整数。
• 如果两个元素 `p` 和 `q` 在 同一行 或者 同一列 ，那么：
• 如果 `p < q` ，那么 `rank(p) < rank(q)`
• 如果 `p == q` ，那么 `rank(p) == rank(q)`
• 如果 `p > q` ，那么 `rank(p) > rank(q)`
•  需要越  越好。

``````输入：matrix = [[1,2],[3,4]]

matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。
``````

``````输入：matrix = [[7,7],[7,7]]

``````

``````输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]

``````

``````输入：matrix = [[7,3,6],[1,4,5],[9,8,2]]

``````

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 500`
• `-109 <= matrix[row][col] <= 109`

• Link: Rank Transform of a Matrix
• Difficulty: Hard
• Tag: `Greedy` `Union Find` `Graph` `Topological Sort` `Array` `Matrix`

Given an `m x n` `matrix`, return a new matrix `answer` where `answer[row][col]` is the rank of `matrix[row][col]`.

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

• The rank is an integer starting from `1`.
• If two elements `p` and `q` are in the same row or column, then:
• If `p < q` then `rank(p) < rank(q)`
• If `p == q` then `rank(p) == rank(q)`
• If `p > q` then `rank(p) > rank(q)`
• The rank should be as small as possible.

The test cases are generated so that `answer` is unique under the given rules.

Example 1:

``````Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
``````

Example 2:

``````Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]
``````

Example 3:

``````Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
``````

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 500`
• `-109 <= matrix[row][col] <= 109`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 500 * 500 + 10;
int n, m, f[N], d[N];
vector<vector<int>> matrix;
vector<vector<int>> G;

int id(int x, int y) {
return x * m + y;
}

struct UFS {
int fa[N], rk[N];
void init(int n) {
memset(fa, -1, sizeof(fa[0]) * (n + 5));
memset(rk, 0, sizeof(rk[0]) * (n + 5));
}
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (rk[fx] > rk[fy])
swap(fx, fy);
fa[fx] = fy;
if (rk[fx] == rk[fy])
++rk[fy];
return true;
}
return false;
}
bool same(int x, int y) {
return find(x) == find(y);
}
} ufs;

void topo() {
queue<int> que;
memset(f, 0, sizeof f);
for (int i = 0; i < n * m; ++i) {
if (d[i] == 0) {
f[i] = 1;
que.push(i);
}
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto &v : G[u]) {
chmax(f[v], f[u] + 1);
if (--d[v] == 0) {
que.push(v);
}
}
}
}

class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>> &_matrix) {
matrix = _matrix;
n = matrix.size();
m = matrix[0].size();
G.clear();
G.resize(N);
memset(d, 0, sizeof d);
ufs.init(N - 10);
for (int i = 0; i < n; ++i) {
vector<pII> vec;
for (int j = 0; j < m; ++j) {
vec.push_back(pII(matrix[i][j], j));
}
sort(all(vec));
for (int j = 1; j < m; ++j) {
if (vec[j].fi == vec[j - 1].fi) {
int u = id(i, vec[j - 1].se);
int v = id(i, vec[j].se);
ufs.merge(u, v);
}
}
}
for (int j = 0; j < m; ++j) {
vector<pII> vec;
for (int i = 0; i < n; ++i) {
vec.push_back(pII(matrix[i][j], i));
}
sort(all(vec));
for (int i = 1; i < n; ++i) {
if (vec[i].fi == vec[i - 1].fi) {
int u = id(vec[i - 1].se, j);
int v = id(vec[i].se, j);
ufs.merge(u, v);
}
}
}
for (int i = 0; i < n; ++i) {
vector<pII> vec;
for (int j = 0; j < m; ++j) {
vec.push_back(pII(matrix[i][j], j));
}
sort(all(vec));
for (int j = 1; j < m; ++j) {
if (vec[j].fi != vec[j - 1].fi) {
int u = ufs.find(id(i, vec[j - 1].se));
int v = ufs.find(id(i, vec[j].se));
G[u].push_back(v);
++d[v];
}
}
}
for (int j = 0; j < m; ++j) {
vector<pII> vec;
for (int i = 0; i < n; ++i) {
vec.push_back(pII(matrix[i][j], i));
}
sort(all(vec));
for (int i = 1; i < n; ++i) {
if (vec[i].fi != vec[i - 1].fi) {
int u = ufs.find(id(vec[i - 1].se, j));
int v = ufs.find(id(vec[i].se, j));
G[u].push_back(v);
++d[v];
}
}
}
topo();
vector<vector<int>> res(n, vector<int>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) res[i][j] = f[ufs.find(id(i, j))];
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````