# weekly-contest-312

## A

### Statement

``````输入：names = ["Mary","John","Emma"], heights = [180,165,170]

``````

``````输入：names = ["Alice","Bob","Bob"], heights = [155,185,150]

``````

• `n == names.length == heights.length`
• `1 <= n <= 103`
• `1 <= names[i].length <= 20`
• `1 <= heights[i] <= 105`
• `names[i]` 由大小写英文字母组成
• `heights` 中的所有值互不相同

You are given an array of strings `names`, and an array `heights` that consists of distinct positive integers. Both arrays are of length `n`.

For each index `i`, `names[i]` and `heights[i]` denote the name and height of the `ith` person.

Return `names` sorted in descending order by the people's heights.

Example 1:

``````Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.
``````

Example 2:

``````Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.
``````

Constraints:

• `n == names.length == heights.length`
• `1 <= n <= 103`
• `1 <= names[i].length <= 20`
• `1 <= heights[i] <= 105`
• `names[i]` consists of lower and upper case English letters.
• All the values of `heights` are distinct.

### 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:
vector<string> sortPeople(vector<string> &names, vector<int> &heights) {
int n = int(names.size());
auto vec = vector<pair<int, string>>();

for (int i = 0; i < n; i++) {
vec.push_back(make_pair(heights[i], names[i]));
}

sort(all(vec));
reverse(all(vec));

auto res = vector<string>();
for (int i = 0; i < n; i++) {
res.push_back(vec[i].second);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 换句话说，令 `k``nums` 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 `k` 的子数组。

``````输入：nums = [1,2,3,3,2,2]

``````

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

``````

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 106`

You are given an integer array `nums` of size `n`.

Consider a non-empty subarray from `nums` that has the maximum possible bitwise AND.

• In other words, let `k` be the maximum value of the bitwise AND of any subarray of `nums`. Then, only subarrays with a bitwise AND equal to `k` should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

``````Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.
``````

Example 2:

``````Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[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

class Solution {
public:
int longestSubarray(vector<int> &nums) {
int mx = *max_element(all(nums));

int cur = 0;
int res = 0;

for (const auto &a : nums) {
if (a == mx) {
++cur;
} else {
cur = 0;
}

res = max(res, cur);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 下标 `i` 之前`k` 个元素是 非递增的 。
• 下标 `i` 之后 的 `k` 个元素是 非递减的 。

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

- 下标 2 。子数组 [2,1] 是非递增的，子数组 [1,3] 是非递减的。
- 下标 3 。子数组 [1,1] 是非递增的，子数组 [3,4] 是非递减的。

``````输入：nums = [2,1,1,2], k = 2

``````

• `n == nums.length`
• `3 <= n <= 105`
• `1 <= nums[i] <= 106`
• `1 <= k <= n / 2`

You are given a 0-indexed integer array `nums` of size `n` and a positive integer `k`.

We call an index `i` in the range `k <= i < n - k` good if the following conditions are satisfied:

• The `k` elements that are just before the index `i` are in non-increasing order.
• The `k` elements that are just after the index `i` are in non-decreasing order.

Return an array of all good indices sorted in increasing order.

Example 1:

``````Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.``````

Example 2:

``````Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.
``````

Constraints:

• `n == nums.length`
• `3 <= n <= 105`
• `1 <= nums[i] <= 106`
• `1 <= k <= n / 2`

### 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:
vector<int> goodIndices(vector<int> &nums, int k) {
int n = int(nums.size());

auto pre = vector<int>(n + 5, 1);
auto suffix = vector<int>(n + 5, 1);

for (int i = 1; i < n; i++) {
if (nums[i] <= nums[i - 1]) {
pre[i] = pre[i - 1] + 1;
}
}

for (int i = n - 2; i >= 0; i--) {
if (nums[i] <= nums[i + 1]) {
suffix[i] = suffix[i + 1] + 1;
}
}

auto res = vector<int>();

for (int i = 1; i < n - 1; i++) {
// cout << i << " " << pre[i - 1] << " " << suffix[i + 1] << endl;
if (pre[i - 1] >= k && suffix[i + 1] >= k) {
res.push_back(i);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

1. 开始节点和结束节点的值 相同 。
2. 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。

``````输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]

（反方向的路径 4 -> 2 -> 0 -> 1 视为跟 1 -> 0 -> 2 -> 4 一样的路径）

``````

``````输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]

``````

``````输入：vals = [1], edges = []

``````

• `n == vals.length`
• `1 <= n <= 3 * 104`
• `0 <= vals[i] <= 105`
• `edges.length == n - 1`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• `edges` 表示一棵合法的树。

There is a tree (i.e. a connected, undirected graph with no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` edges.

You are given a 0-indexed integer array `vals` of length `n` where `vals[i]` denotes the value of the `ith` node. You are also given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an undirected edge connecting nodes `ai` and `bi`.

A good path is a simple path that satisfies the following conditions:

1. The starting node and the ending node have the same value.
2. All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node's value should be the maximum value along the path).

Return the number of distinct good paths.

Note that a path and its reverse are counted as the same path. For example, `0 -> 1` is considered to be the same as `1 -> 0`. A single node is also considered as a valid path.

Example 1:

``````Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
Explanation: There are 5 good paths consisting of a single node.
There is 1 additional good path: 1 -> 0 -> 2 -> 4.
(The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.)
Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].
``````

Example 2:

``````Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 7
Explanation: There are 5 good paths consisting of a single node.
There are 2 additional good paths: 0 -> 1 and 2 -> 3.
``````

Example 3:

``````Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.
``````

Constraints:

• `n == vals.length`
• `1 <= n <= 3 * 104`
• `0 <= vals[i] <= 105`
• `edges.length == n - 1`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• `edges` represents a valid tree.

### 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

const int N = 3e4 + 10;

struct UFS {
int fa[N];
unordered_map<int, int> mp[N];

void init(int n) {
for (int i = 0; i <= n; i++) {
fa[i] = 0;
mp[i].clear();
}
}

int find(int x) {
return fa[x] == 0 ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy;

for (const auto &[k, v] : mp[fx]) {
mp[fy][k] += v;
}

return true;
}

return false;
}
} ufs;

class Solution {
public:
int numberOfGoodPaths(vector<int> &vals, vector<vector<int>> &edges) {
int n = int(vals.size());

ufs.init(n);

auto node = vector<pair<int, int>>();
for (int i = 0; i < n; i++) {
node.push_back(make_pair(vals[i], i + 1));
}

auto graph = vector<vector<int>>(n + 5, vector<int>());

for (const auto &e : edges) {
graph[e[0] + 1].push_back(e[1] + 1);
graph[e[1] + 1].push_back(e[0] + 1);
}

auto ok_node = vector<int>(n + 1, 0);

int res = 0;

sort(all(node));

for (int i = 0; i < n; i++) {
int _val = node[i].first;
int r = i;

for (int j = i; j < n; j++) {
int val = node[j].first;
if (val != _val) {
break;
}

int u = node[j].second;

r = j;

ok_node[u] = 1;
ufs.mp[u][val] = 1;

for (const auto &v : graph[u]) {
if (ok_node[v]) {
ufs.merge(u, v);
}
}
}

for (int j = i; j <= r; j++) {
int val = node[j].first;
int u = node[j].second;

int rt = ufs.find(u);
auto &mp = ufs.mp[rt];

int tot = mp[val];
res += tot;
}

i = r;
}

res -= (res - n) / 2;

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````