# biweekly-contest-87

## A

### Statement

Alice 和 Bob 计划分别去罗马开会。

输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"



输入：arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"



• 所有日期的格式均为 "MM-DD" 。
• Alice 和 Bob 的到达日期都 早于或等于 他们的离开日期。
• 题目测试用例所给出的日期均为 非闰年 的有效日期。

Alice and Bob are traveling to Rome for separate business meetings.

You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.

Return the total number of days that Alice and Bob are in Rome together.

You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].

Example 1:

Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
Output: 3
Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.


Example 2:

Input: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
Output: 0
Explanation: There is no day when Alice and Bob are in Rome together, so we return 0.


Constraints:

• All dates are provided in the format "MM-DD".
• Alice and Bob's arrival dates are earlier than or equal to their leaving dates.
• The given dates are valid dates of a non-leap year.

### 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 countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
int res = 0;

auto mon = vector<int>({0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31});
auto mp = map<pair<int, int>, int>();

auto g = [](char c) {
return c - '0';
};

auto f = [&g, &mp, &mon](const std::string &st_str, const std::string &ed_str) {
auto st = make_pair(g(st_str[0]) * 10 + g(st_str[1]), g(st_str[3]) * 10 + g(st_str[4]));
auto ed = make_pair(g(ed_str[0]) * 10 + g(ed_str[1]), g(ed_str[3]) * 10 + g(ed_str[4]));

while (true) {
mp[st] += 1;
if (st == ed) {
break;
}

++st.second;
if (st.second > mon[st.first]) {
++st.first;
st.second = 1;
}
}
};

f(arriveAlice, leaveAlice);
f(arriveBob, leaveBob);

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

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif


## B

### Statement

输入：players = [4,7,9], trainers = [8,2,5,8]

- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。



输入：players = [1,1,1], trainers = [10]



• 1 <= players.length, trainers.length <= 105
• 1 <= players[i], trainers[j] <= 109

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions.

Example 1:

Input: players = [4,7,9], trainers = [8,2,5,8]
Output: 2
Explanation:
One of the ways we can form two matchings is as follows:
- players[0] can be matched with trainers[0] since 4 <= 8.
- players[1] can be matched with trainers[3] since 7 <= 8.
It can be proven that 2 is the maximum number of matchings that can be formed.


Example 2:

Input: players = [1,1,1], trainers = [10]
Output: 1
Explanation:
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.


Constraints:

• 1 <= players.length, trainers.length <= 105
• 1 <= players[i], trainers[j] <= 109

### 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 matchPlayersAndTrainers(vector<int> &players, vector<int> &trainers) {
sort(all(players));
sort(all(trainers));

int n = int(players.size());
int i = 0;

int res = 0;

for (const auto &t : trainers) {
if (i >= n) {
break;
}

if (t >= players[i]) {
++res;
++i;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif


## C

### Statement

• 换言之，令 Bij 表示子数组 nums[i…j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

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

- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。



输入：nums = [1,2]



• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.

• In other words, let Bij be the bitwise OR of the subarray nums[i…j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= k <= n - 1.

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

Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.

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

Example 1:

Input: nums = [1,0,2,1,3]
Output: [3,3,2,2,1]
Explanation:
The maximum possible bitwise OR starting at any index is 3.
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1].


Example 2:

Input: nums = [1,2]
Output: [2,1]
Explanation:
Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].


Constraints:

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

### 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> smallestSubarrays(vector<int> &nums) {
int n = int(nums.size());
auto res = vector<int>(n, 0);
auto f = vector<int>(35, 0);

int r = n - 1;

const auto add = [&f](int x) {
for (int i = 0; i < 31; i++) {
f[i] += ((x >> i) & 1);
}
};

const auto tryDel = [&f](int x) {
bool ok = true;
for (int i = 0; i < 31; i++) {
if ((x >> i) & 1) {
if (f[i] < 2) {
ok = false;
break;
}
}
}

if (ok) {
for (int i = 0; i < 31; i++) {
f[i] -= ((x >> i) & 1);
}
}

return ok;
};

for (int i = n - 1; i >= 0; i--) {
while (r > i) {
if (tryDel(nums[r])) {
--r;
} else {
break;
}
}

res[i] = (r - i + 1);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif


## D

### Statement

输入：transactions = [[2,1],[5,0],[4,2]]



输入：transactions = [[3,0],[0,3]]

- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。



• 1 <= transactions.length <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

You are given a 0-indexed 2D integer array transactions, where transactions[i] = [costi, cashbacki].

The array describes transactions, where each transaction must be completed exactly once in some order. At any given moment, you have a certain amount of money. In order to complete transaction i, money >= costi must hold true. After performing a transaction, money becomes money - costi + cashbacki.

Return the minimum amount of money required before any transaction so that all of the transactions can be completed regardless of the order of the transactions.

Example 1:

Input: transactions = [[2,1],[5,0],[4,2]]
Output: 10
Explanation:
Starting with money = 10, the transactions can be performed in any order.
It can be shown that starting with money < 10 will fail to complete all transactions in some order.


Example 2:

Input: transactions = [[3,0],[0,3]]
Output: 3
Explanation:
- If transactions are in the order [[3,0],[0,3]], the minimum money required to complete the transactions is 3.
- If transactions are in the order [[0,3],[3,0]], the minimum money required to complete the transactions is 0.
Thus, starting with money = 3, the transactions can be performed in any order.


Constraints:

• 1 <= transactions.length <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

### 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:
long long minimumMoney(vector<vector<int>> &transactions) {
int n = int(transactions.size());

ll res = 0;

ll gap_sum = 0;

for (int i = 0; i < n; i++) {
const auto &t = transactions[i];

ll gap = t[1] - t[0];
if (gap < 0) {
gap_sum += -gap;
}
}

for (int i = 0; i < n; i++) {
const auto &t = transactions[i];

ll gap = t[1] - t[0];
if (gap < 0) {
gap_sum -= -gap;
}

res = max(res, t[0] + gap_sum);

if (gap < 0) {
gap_sum += -gap;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif