# biweekly-contest-82

## A

### Statement

• 叶子节点 要么值为 `0` 要么值为 `1` ，其中 `0` 表示 `False` ，`1` 表示 `True` 。
• 非叶子节点 要么值为 `2` 要么值为 `3` ，其中 `2` 表示逻辑或 `OR``3` 表示逻辑与 `AND` 。

• 如果节点是个叶子节点，那么节点的  为它本身，即 `True` 或者 `False` 。
• 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。

``````输入：root = [2,1,3,null,null,0,1]

AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。

``````输入：root = [0]

``````

• 树中节点数目在 `[1, 1000]` 之间。
• `0 <= Node.val <= 3`
• 每个节点的孩子数为 `0` 或 `2` 。
• 叶子节点的值为 `0` 或 `1` 。
• 非叶子节点的值为 `2` 或 `3`

You are given the `root` of a full binary tree with the following properties:

• Leaf nodes have either the value `0` or `1`, where `0` represents `False` and `1` represents `True`.
• Non-leaf nodes have either the value `2` or `3`, where `2` represents the boolean `OR` and `3` represents the boolean `AND`.

The evaluation of a node is as follows:

• If the node is a leaf node, the evaluation is the value of the node, i.e. `True` or `False`.
• Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

Return the boolean result of evaluating the `root` node.

A full binary tree is a binary tree where each node has either `0` or `2` children.

A leaf node is a node that has zero children.

Example 1:

``````Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.``````

Example 2:

``````Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 1000]`.
• `0 <= Node.val <= 3`
• Every node has either `0` or `2` children.
• Leaf nodes have a value of `0` or `1`.
• Non-leaf nodes have a value of `2` or `3`.

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

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

#ifdef LOCAL

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#endif

class Solution {
public:
bool dfs(TreeNode *root) {
if (!root->left && !root->right) {
return root->val;
}

if (root->val == 2) {
return dfs(root->left) || dfs(root->right);
}

return dfs(root->left) && dfs(root->right);
}

bool evaluateTree(TreeNode *root) {
return dfs(root);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2

``````输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2

``````

• `n == buses.length`
• `m == passengers.length`
• `1 <= n, m, capacity <= 105`
• `2 <= buses[i], passengers[i] <= 109`
• `buses` 中的元素 互不相同
• `passengers` 中的元素 互不相同 。

You are given a 0-indexed integer array `buses` of length `n`, where `buses[i]` represents the departure time of the `ith` bus. You are also given a 0-indexed integer array `passengers` of length `m`, where `passengers[j]` represents the arrival time of the `jth` passenger. All bus departure times are unique. All passenger arrival times are unique.

You are given an integer `capacity`, which represents the maximum number of passengers that can get on each bus.

The passengers will get on the next available bus. You can get on a bus that will depart at `x` minutes if you arrive at `y` minutes where `y <= x`, and the bus is not full. Passengers with the earliest arrival times get on the bus first.

Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.

Note: The arrays `buses` and `passengers` are not necessarily sorted.

Example 1:

``````Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2
Output: 16
Explanation:
The 1st bus departs with the 1st passenger.
The 2nd bus departs with you and the 2nd passenger.
Note that you must not arrive at the same time as the passengers, which is why you must arrive before the 2nd passenger to catch the bus.``````

Example 2:

``````Input: buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
Output: 20
Explanation:
The 1st bus departs with the 4th passenger.
The 2nd bus departs with the 6th and 2nd passengers.
The 3rd bus departs with the 1st passenger and you.
``````

Constraints:

• `n == buses.length`
• `m == passengers.length`
• `1 <= n, m, capacity <= 105`
• `2 <= buses[i], passengers[i] <= 109`
• Each element in `buses` is unique.
• Each element in `passengers` is unique.

### 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 latestTimeCatchTheBus(vector<int> &buses, vector<int> &passengers, int capacity) {
sort(all(buses));
sort(all(passengers));

int n = int(buses.size());
int m = int(passengers.size());

auto vis = map<int, bool>();

int res = 1;
for (int i = 0, j = -1; i < n; ++i) {
int o = 0;
for (; o < capacity && j + 1 < m && passengers[j + 1] <= buses[i];) {
o++;
j++;

vis[passengers[j]] = 1;
if (vis[passengers[j] - 1] == 0) {
res = max(res, passengers[j] - 1);
}
}

if (o + 1 <= capacity && vis[buses[i]] == 0) {
res = max(res, buses[i]);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0

``````

``````输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1

- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。

(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43 。

• `n == nums1.length == nums2.length`
• `1 <= n <= 105`
• `0 <= nums1[i], nums2[i] <= 105`
• `0 <= k1, k2 <= 109`

You are given two positive 0-indexed integer arrays `nums1` and `nums2`, both of length `n`.

The sum of squared difference of arrays `nums1` and `nums2` is defined as the sum of `(nums1[i] - nums2[i])2` for each `0 <= i < n`.

You are also given two positive integers `k1` and `k2`. You can modify any of the elements of `nums1` by `+1` or `-1` at most `k1` times. Similarly, you can modify any of the elements of `nums2` by `+1` or `-1` at most `k2` times.

Return the minimum sum of squared difference after modifying array `nums1` at most `k1` times and modifying array `nums2` at most `k2` times.

Note: You are allowed to modify the array elements to become negative integers.

Example 1:

``````Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0.
The sum of square difference will be: (1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579.
``````

Example 2:

``````Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: One way to obtain the minimum sum of square difference is:
- Increase nums1[0] once.
- Increase nums2[2] once.
The minimum of the sum of square difference will be:
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43.
Note that, there are other ways to obtain the minimum of the sum of square difference, but there is no way to obtain a sum smaller than 43.``````

Constraints:

• `n == nums1.length == nums2.length`
• `1 <= n <= 105`
• `0 <= nums1[i], nums2[i] <= 105`
• `0 <= k1, k2 <= 109`

### Solution

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

#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:
long long minSumSquareDiff(vector<int> &nums1, vector<int> &nums2, int k1, int k2) {
int n = (int)(nums1.size());

vector<int> f;
f.reserve(n);
for (int i = 0; i < n; i++) {
f.push_back(abs(nums1[i] - nums2[i]));
}
f.push_back(0);
sort(all(f));

priority_queue<int, vector<int>, less<int>> pq;

ll k = k1 + k2;

int cnt = 1;
ll num = f[n];
for (int i = n - 1; i >= 0; i--) {
ll c = (num - f[i]) * cnt;

if (k >= c) {
k -= c;
++cnt;
num = f[i];
} else {
ll x = k / cnt;
num -= x;
k -= x * cnt;

for (int j = 0; j <= i; j++) {
pq.push(f[j]);
}

for (int j = 1; j <= cnt; j++) {
pq.push(int(num));
}

break;
}
}

if (cnt == n + 1) {
for (int j = 1; j <= cnt; j++) {
pq.push(int(num));
}
}

while (k && !pq.empty()) {
auto t = pq.top();
pq.pop();

if (t > 0) {
pq.push(t - 1);
k--;
}
}

ll res = 0;
while (!pq.empty()) {
int x = pq.top();
pq.pop();

res += 1ll * x * x;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

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

``````

``````输入：nums = [6,5,6,5,8], threshold = 7

• `1 <= nums.length <= 105`
• `1 <= nums[i], threshold <= 109`

You are given an integer array `nums` and an integer `threshold`.

Find any subarray of `nums` of length `k` such that every element in the subarray is greater than `threshold / k`.

Return the size of any such subarray. If there is no such subarray, return `-1`.

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

Example 1:

``````Input: nums = [1,3,4,3,1], threshold = 6
Output: 3
Explanation: The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.
``````

Example 2:

``````Input: nums = [6,5,6,5,8], threshold = 7
Output: 1
Explanation: The subarray [8] has a size of 1, and 8 > 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5.
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i], threshold <= 109`

### Solution

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

#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 = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int th, res;

struct Cartesian_Tree {
struct node {
int id, val, fa;
int son[2];
node() {}
node(int id, int val, int fa) : id(id), val(val), fa(fa) {
son[0] = son[1] = 0;
}
bool operator<(const node &other) const {
return val < other.val;
}
} t[N];

int root;
void init() {
t[0] = node(0, -INF, 0);
}

void build(vector<int> &a) {
int n = int(a.size());
for (int i = 1; i <= n; ++i) {
t[i] = node(i, a[i - 1], 0);
}

for (int i = 1; i <= n; ++i) {
int k = i - 1;
while (t[i] < t[k]) {
k = t[k].fa;
}

t[i].son[0] = t[k].son[1];

t[k].son[1] = i;

t[i].fa = k;

t[t[i].son[0]].fa = i;
}
root = t[0].son[1];
}
int DFS(int u) {
if (!u)
return 0;

int sze = DFS(t[u].son[0]) + DFS(t[u].son[1]) + 1;
if (t[u].val > th / sze) {
res = sze;
}

return sze;
}
} CT;

class Solution {
public:
int validSubarraySize(vector<int> &nums, int threshold) {
CT.init();
CT.build(nums);
res = -1;
th = threshold;
CT.DFS(CT.root);

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````