# weekly-contest-323

## A

### Statement

• 从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。
• 将删除元素中的最大值与答案相加。

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

- 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们可以删除任一）。在答案上加 4 。
- 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。
- 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。

``````

``````输入：grid = [[10]]

- 在第一步操作中，从第一行删除 10 。在答案上加 10 。

``````

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 50`
• `1 <= grid[i][j] <= 100`

You are given an `m x n` matrix `grid` consisting of positive integers.

Perform the following operation until `grid` becomes empty:

• Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Example 1:

``````Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
The final answer = 4 + 3 + 1 = 8.
``````

Example 2:

``````Input: grid = [[10]]
Output: 10
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
``````

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 50`
• `1 <= grid[i][j] <= 100`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int deleteGreatestValue(vector<vector<int>> &grid) {
int n = int(grid.size());
int m = int(grid[0].size());

int ans = 0;

for (int i = 0; i < n; i++) {
sort(all(grid[i]));
}

for (int j = 0; j < m; j++) {
int mx = 0;
for (int i = 0; i < n; i++) {
mx = max(mx, grid[i][j]);
}

ans += mx;
}

return ans;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 子序列的长度至少为 `2` ，并且
• 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方

``````输入：nums = [4,3,6,16,8,2]

- 4 = 2 * 2.
- 16 = 4 * 4.

``````

``````输入：nums = [2,3,5,6,7]

``````

• `2 <= nums.length <= 105`
• `2 <= nums[i] <= 105`

You are given an integer array `nums`. A subsequence of `nums` is called a square streak if:

• The length of the subsequence is at least `2`, and
• after sorting the subsequence, each element (except the first element) is the square of the previous number.

Return the length of the longest square streak in `nums`, or return `-1` if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

``````Input: nums = [4,3,6,16,8,2]
Output: 3
Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.
``````

Example 2:

``````Input: nums = [2,3,5,6,7]
Output: -1
Explanation: There is no square streak in nums so return -1.
``````

Constraints:

• `2 <= nums.length <= 105`
• `2 <= nums[i] <= 105`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int longestSquareStreak(vector<int> &nums) {
sort(all(nums));

auto mp = map<int, int>();
for (const auto &a : nums) {
int x = int(sqrt(a));
if (x * x == a) {
mp[a] = mp[x] + 1;
} else {
mp[a] = 1;
}
}

int res = 0;

for (const auto &[k, v] : mp) {
res = max(res, v);
}

return res == 1 ? -1 : res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

1. 分配 一块大小为 `size` 的连续空闲内存单元并赋 id `mID`
2. 释放 给定 id `mID` 对应的所有内存单元。

• 多个块可以被分配到同一个 `mID`
• 你必须释放 `mID` 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

• `Allocator(int n)` 使用一个大小为 `n` 的内存数组初始化 `Allocator` 对象。
• `int allocate(int size, int mID)` 找出大小为 `size` 个连续空闲内存单元且位于  最左侧 的块，分配并赋 id `mID` 。返回块的第一个下标。如果不存在这样的块，返回 `-1`
• `int free(int mID)` 释放 id `mID` 对应的所有内存单元。返回释放的内存单元数目。

``````输入
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]

[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。
``````

• `1 <= n, size, mID <= 1000`
• 最多调用 `allocate``free` 方法 `1000`

You are given an integer `n` representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

1. Allocate a block of `size` consecutive free memory units and assign it the id `mID`.
2. Free all memory units with the given id `mID`.

Note that:

• Multiple blocks can be allocated to the same `mID`.
• You should free all the memory units with `mID`, even if they were allocated in different blocks.

Implement the `Allocator` class:

• `Allocator(int n)` Initializes an `Allocator` object with a memory array of size `n`.
• `int allocate(int size, int mID)` Find the leftmost block of `size` consecutive free memory units and allocate it with the id `mID`. Return the block's first index. If such a block does not exist, return `-1`.
• `int free(int mID)` Free all memory units with the id `mID`. Return the number of memory units you have freed.

Example 1:

``````Input
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
Output
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]
Explanation
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,,,,,,,,,]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,,,,,,,,]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,,,,,,,]. We return 2.
loc.free(2); // Free all memory units with mID 2. The memory array becomes [1,, 3,,,,,,,]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,,3,4,4,4,,,,]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,,,,]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,,,]. We return 6.
loc.free(1); // Free all memory units with mID 1. The memory array becomes [,,3,4,4,4,,,,]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.free(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.
``````

Constraints:

• `1 <= n, size, mID <= 1000`
• At most `1000` calls will be made to `allocate` and `free`.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Allocator {
public:
vector<int> mem;
int n;

Allocator(int n) {
this->n = n;
mem = vector<int>(n + 5, 0);
}

int allocate(int size, int mID) {
for (int i = 0; i < n && i + size <= n; i++) {
if (mem[i] != 0) {
continue;
}

int ok = 1;

for (int j = i; j - i < size; j++) {
if (mem[j] != 0) {
i = j;
ok = 0;
break;
}
}

if (ok) {
for (int j = i; j - i < size; j++) {
mem[j] = mID;
}

return i;
}
}

return -1;
}

int free(int mID) {
int cnt = 0;

for (int i = 0; i < n; i++) {
if (mem[i] == mID) {
mem[i] = 0;
++cnt;
}
}

return cnt;
}
};

/**
* Your Allocator object will be instantiated and called as such:
* Allocator* obj = new Allocator(n);
* int param_1 = obj->allocate(size,mID);
* int param_2 = obj->free(mID);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 如果 `queries[i]` 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 `4` 个方向（上、下、左、右）上任一 相邻 单元格。
• 否则，你不能获得任何分，并且结束这一过程。

``````输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]

``````输入：grid = [[5,2,1],[1,1,2]], queries = [3]

``````

• `m == grid.length`
• `n == grid[i].length`
• `2 <= m, n <= 1000`
• `4 <= m * n <= 105`
• `k == queries.length`
• `1 <= k <= 104`
• `1 <= grid[i][j], queries[i] <= 106`

You are given an `m x n` integer matrix `grid` and an array `queries` of size `k`.

Find an array `answer` of size `k` such that for each integer `queres[i]` you start in the top left cell of the matrix and repeat the following process:

• If `queries[i]` is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all `4` directions: up, down, left, and right.
• Otherwise, you do not get any points, and you end this process.

After the process, `answer[i]` is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array `answer`.

Example 1:

``````Input: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
Output: [5,8,1]
Explanation: The diagrams above show which cells we visit to get points for each query.``````

Example 2:

``````Input: grid = [[5,2,1],[1,1,2]], queries = [3]
Output: [0]
Explanation: We can not get any points because the value of the top left cell is already greater than or equal to 3.
``````

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `2 <= m, n <= 1000`
• `4 <= m * n <= 105`
• `k == queries.length`
• `1 <= k <= 104`
• `1 <= grid[i][j], queries[i] <= 106`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

struct QNode {
int ix;
int v;
};

const int N = 1e5 + 10;

struct UFS {
int fa[N], sze[N];
void init(int n) {
memset(fa, -1, sizeof(fa[0]) * (n + 5));

for (int i = 0; i <= n; i++) {
sze[i] = 1;
}
}

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 (sze[fx] > sze[fy]) {
swap(fx, fy);
}

fa[fx] = fy;
sze[fy] += sze[fx];

return true;
}

return false;
}
bool same(int x, int y) {
return find(x) == find(y);
}
} ufs;

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

class Solution {
public:
int n, m;

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

vector<int> maxPoints(vector<vector<int>> &grid, vector<int> &queries) {
int n = int(grid.size());
int m = int(grid[0].size());
int q = int(queries.size());

this->n = n;
this->m = m;

int nn = n * m;

ufs.init(nn + 5);

auto node = vector<tuple<int, int, int>>();

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
node.push_back(make_tuple(grid[i][j], i, j));
}
}

sort(all(node));

auto qq = vector<tuple<int, int>>();
for (int i = 0; i < q; i++) {
qq.push_back(make_tuple(queries[i], i));
}

sort(all(qq));

auto res = vector<int>(q, 0);

for (int i = 0, ix = 0; i < q; i++) {
const auto [qv, qx] = qq[i];

while (ix < nn && get<0>(node[ix]) < qv) {
const auto [v, x, y] = node[ix];

for (int j = 0; j < 4; j++) {
int nx = x + mv[j][0];
int ny = y + mv[j][1];

if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] < qv) {
ufs.merge(id(x, y), id(nx, ny));
}
}

++ix;
}

if (qv > grid[0][0]) {
res[qx] = ufs.sze[ufs.find(0)];
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````