# biweekly-contest-95

## A

### Statement

• 如果满足以下条件，那么箱子是 `"Bulky"` 的：
• 箱子 至少有一个 维度大于等于 `104` 。
• 或者箱子的 体积 大于等于 `109` 。
• 如果箱子的质量大于等于 `100` ，那么箱子是 `"Heavy"` 的。
• 如果箱子同时是 `"Bulky"` 和 `"Heavy"` ，那么返回类别为 `"Both"` 。
• 如果箱子既不是 `"Bulky"` ，也不是 `"Heavy"` ，那么返回类别为 `"Neither"` 。
• 如果箱子是 `"Bulky"` 但不是 `"Heavy"` ，那么返回类别为 `"Bulky"` 。
• 如果箱子是 `"Heavy"` 但不是 `"Bulky"` ，那么返回类别为 `"Heavy"` 。

``````输入：length = 1000, width = 35, height = 700, mass = 300

``````输入：length = 200, width = 50, height = 800, mass = 50

• `1 <= length, width, height <= 105`
• `1 <= mass <= 103`

Given four integers `length`, `width`, `height`, and `mass`, representing the dimensions and mass of a box, respectively, return a string representing the category of the box.

• The box is `"Bulky"` if:
• Any of the dimensions of the box is greater or equal to `104`.
• Or, the volume of the box is greater or equal to `109`.
• If the mass of the box is greater or equal to `100`, it is `"Heavy".`
• If the box is both `"Bulky"` and `"Heavy"`, then its category is `"Both"`.
• If the box is neither `"Bulky"` nor `"Heavy"`, then its category is `"Neither"`.
• If the box is `"Bulky"` but not `"Heavy"`, then its category is `"Bulky"`.
• If the box is `"Heavy"` but not `"Bulky"`, then its category is `"Heavy"`.

Note that the volume of the box is the product of its length, width and height.

Example 1:

``````Input: length = 1000, width = 35, height = 700, mass = 300
Output: "Heavy"
Explanation:
None of the dimensions of the box is greater or equal to 104.
Its volume = 24500000 <= 109. So it cannot be categorized as "Bulky".
However mass >= 100, so the box is "Heavy".
Since the box is not "Bulky" but "Heavy", we return "Heavy".``````

Example 2:

``````Input: length = 200, width = 50, height = 800, mass = 50
Output: "Neither"
Explanation:
None of the dimensions of the box is greater or equal to 104.
Its volume = 8 * 106 <= 109. So it cannot be categorized as "Bulky".
Its mass is also less than 100, so it cannot be categorized as "Heavy" either.
Since its neither of the two above categories, we return "Neither".``````

Constraints:

• `1 <= length, width, height <= 105`
• `1 <= mass <= 103`

### 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:
string categorizeBox(int l, int w, int h, int mass) {
const int E2 = 1e2;
const int E4 = 1e4;
const int E9 = 1e9;

ll v = 1ll * l * w * h;

bool b = (l >= E4 || w >= E4 || h >= E4 || v >= E9);
bool e = (mass >= E2);

if (b && e) {
return "Both";
}

if (!b && !e) {
return "Neither";
}

if (b) {
return "Bulky";
}

if (e) {
return "Heavy";
}

return "";
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• `DataStream(int value, int k)` 用两个整数 `value` 和 `k` 初始化一个空的整数数据流。
• `boolean consec(int num)` 将 `num` 添加到整数数据流。如果后 `k` 个整数都等于 `value` ，返回 `true` ，否则返回 `false` 。如果少于 `k` 个整数，条件不满足，所以也返回 `false` 。

``````输入：
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]

[null, false, false, true, false]

DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3
dataStream.consec(4); // 数据流中只有 1 个整数，所以返回 False 。
dataStream.consec(4); // 数据流中只有 2 个整数
// 由于 2 小于 k ，返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value， 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3] 。
// 由于 3 不等于 value ，返回 False 。
``````

• `1 <= value, num <= 109`
• `1 <= k <= 105`
• 至多调用 `consec` 次数为 `105` 次。

For a stream of integers, implement a data structure that checks if the last `k` integers parsed in the stream are equal to `value`.

Implement the DataStream class:

• `DataStream(int value, int k)` Initializes the object with an empty integer stream and the two integers `value` and `k`.
• `boolean consec(int num)` Adds `num` to the stream of integers. Returns `true` if the last `k` integers are equal to `value`, and `false` otherwise. If there are less than `k` integers, the condition does not hold true, so returns `false`.

Example 1:

``````Input
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
Output
[null, false, false, true, false]
Explanation
DataStream dataStream = new DataStream(4, 3); //value = 4, k = 3
dataStream.consec(4); // Only 1 integer is parsed, so returns False.
dataStream.consec(4); // Only 2 integers are parsed.
// Since 2 is less than k, returns False.
dataStream.consec(4); // The 3 integers parsed are all equal to value, so returns True.
dataStream.consec(3); // The last k integers parsed in the stream are [4,4,3].
// Since 3 is not equal to value, it returns False.
``````

Constraints:

• `1 <= value, num <= 109`
• `1 <= k <= 105`
• At most `105` calls will be made to `consec`.

### 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 DataStream {
public:
int value{0};
int k{0};
int has{0};
queue<int> q;

DataStream(int value, int k) {
this->value = value;
this->k = k;
this->has = 0;
}

bool consec(int num) {
if (num == value) {
++has;
}

q.push(num);
while (q.size() > size_t(k)) {
int x = q.front();
q.pop();

if (x == value) {
--has;
}
}

return has == k;
}
};

/**
* Your DataStream object will be instantiated and called as such:
* DataStream* obj = new DataStream(value, k);
* bool param_1 = obj->consec(num);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• `val1 | val2` 是 `val1` 和 `val2` 的按位或。
• `val1 & val2` 是 `val1` 和 `val2` 的按位与。

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

- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4

``````输入：nums = [15,45,20,2,34,35,5,44,32,30]

``````

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

You are given a 0-indexed integer array `nums`.

The effective value of three indices `i`, `j`, and `k` is defined as `((nums[i] | nums[j]) & nums[k])`.

The xor-beauty of the array is the XORing of the effective values of all the possible triplets of indices `(i, j, k)` where `0 <= i, j, k < n`.

Return the xor-beauty of `nums`.

Note that:

• `val1 | val2` is bitwise OR of `val1` and `val2`.
• `val1 & val2` is bitwise AND of `val1` and `val2`.

Example 1:

``````Input: nums = [1,4]
Output: 5
Explanation:
The triplets and their corresponding effective values are listed below:
- (0,0,0) with effective value ((1 | 1) & 1) = 1
- (0,0,1) with effective value ((1 | 1) & 4) = 0
- (0,1,0) with effective value ((1 | 4) & 1) = 1
- (0,1,1) with effective value ((1 | 4) & 4) = 4
- (1,0,0) with effective value ((4 | 1) & 1) = 1
- (1,0,1) with effective value ((4 | 1) & 4) = 4
- (1,1,0) with effective value ((4 | 4) & 1) = 0
- (1,1,1) with effective value ((4 | 4) & 4) = 4
Xor-beauty of array will be bitwise XOR of all beauties = 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5.``````

Example 2:

``````Input: nums = [15,45,20,2,34,35,5,44,32,30]
Output: 34
Explanation: The xor-beauty of the given array is 34.
``````

Constraints:

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

// 1 1 0 1

class Solution {
public:
ll s(int x) {
return 1ll * x * x;
}

int xorBeauty(vector<int> &nums) {
int n = int(nums.size());
auto f = vector<int>(50, 0);

for (int x : nums) {
for (int j = 0; j < 31; j++) {
if ((x >> j) & 1) {
++f[j];
}
}
}

int res = 0;
for (const auto &x : nums) {
int cur_res = 0;

for (int j = 0; j < 31; j++) {
int b = (x >> j) & 1;
if (b) {
ll r = s(n) - s(n - f[j]);
if (r & 1) {
cur_res |= (1 << j);
}
}
}

res ^= cur_res;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• `|x|` 表示 `x` 的 绝对值 。比方说，`|7 - 5| = 2` ，`|3 - 10| = 7` 。

`k` 座供电站可以建在多个城市。

``````输入：stations = [1,2,4,5,0], r = 1, k = 2

- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。

``````

``````输入：stations = [4,4,4,4], r = 0, k = 3

``````

• `n == stations.length`
• `1 <= n <= 105`
• `0 <= stations[i] <= 105`
• `0 <= r <= n - 1`
• `0 <= k <= 109`

You are given a 0-indexed integer array `stations` of length `n`, where `stations[i]` represents the number of power stations in the `ith` city.

Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by `r`, then a power station at city `i` can provide power to all cities `j` such that `|i - j| <= r` and `0 <= i, j <= n - 1`.

• Note that `|x|` denotes absolute value. For example, `|7 - 5| = 2` and `|3 - 10| = 7`.

The power of a city is the total number of power stations it is being provided power from.

The government has sanctioned building `k` more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.

Given the two integers `r` and `k`, return the maximum possible minimum power of a city, if the additional power stations are built optimally.

Note that you can build the `k` power stations in multiple cities.

Example 1:

``````Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation:
One of the optimal ways is to install both the power stations at city 1.
So stations will become [1,4,4,5,0].
- City 0 is provided by 1 + 4 = 5 power stations.
- City 1 is provided by 1 + 4 + 4 = 9 power stations.
- City 2 is provided by 4 + 4 + 5 = 13 power stations.
- City 3 is provided by 5 + 4 = 9 power stations.
- City 4 is provided by 5 + 0 = 5 power stations.
So the minimum power of a city is 5.
Since it is not possible to obtain a larger power, we return 5.
``````

Example 2:

``````Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation:
It can be proved that we cannot make the minimum power of a city greater than 4.
``````

Constraints:

• `n == stations.length`
• `1 <= n <= 105`
• `0 <= stations[i] <= 105`
• `0 <= r <= n - 1`
• `0 <= k <= 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

const ll INF = 0x3f3f3f3f3f3f3f3f;

class Solution {
public:
long long maxPower(vector<int> &sta, int r, int k) {
int n = int(sta.size());

auto need_ori = vector<ll>(n + 5, 0);
for (int i = 0; i < n; i++) {
int _l = max(0, i - r);
int _r = min(n, i + r + 1);
need_ori[_l] += sta[i];
need_ori[_r] -= sta[i];
}

auto ok = [&](ll x) -> bool {
ll cur = 0;
auto need = need_ori;
ll has = k;

for (int i = 0; i < n; i++) {
cur += need[i];

if (cur >= x) {
continue;
}

ll diff = x - cur;
if (has < diff) {
return false;
}

has -= diff;

int pos = min(n, i + r + r + 1);
need[pos] -= diff;

cur += diff;
}

return true;
};

ll l = 0, rr = INF, res = -1;
while (rr - l >= 0) {
ll mid = (l + rr) >> 1;
if (ok(mid)) {
l = mid + 1;
res = mid;
} else {
rr = mid - 1;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````