# weekly-contest-321

## A

### Statement

• `1``x` 之间的所有元素之和等于 `x``n` 之间所有元素之和。

``````输入：n = 8

``````

``````输入：n = 1

``````

``````输入：n = 4

• `1 <= n <= 1000`

Given a positive integer `n`, find the pivot integer `x` such that:

• The sum of all elements between `1` and `x` inclusively equals the sum of all elements between `x` and `n` inclusively.

Return the pivot integer `x`. If no such integer exists, return `-1`. It is guaranteed that there will be at most one pivot index for the given input.

Example 1:

``````Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
``````

Example 2:

``````Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.
``````

Example 3:

``````Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.
``````

Constraints:

• `1 <= n <= 1000`

### 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 pivotInteger(int n) {
int res = -1;
int sum = 0;
int remind = ((n * (n + 1))) / 2;
for (int i = 1; i <= n; i++) {
sum += i;
if (sum == remind) {
res = i;
}
remind -= i;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：s = "coaching", t = "coding"

``````

``````输入：s = "abcde", t = "a"

``````

``````输入：s = "z", t = "abcde"

``````

• `1 <= s.length, t.length <= 105`
• `s``t` 仅由小写英文字母组成

You are given two strings `s` and `t` consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of `s` so that `t` becomes a subsequence of `s`.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

``````Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.
``````

Example 2:

``````Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").
``````

Example 3:

``````Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.
``````

Constraints:

• `1 <= s.length, t.length <= 105`
• `s` and `t` consist only of lowercase English letters.

### 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 ALP = 26;
const int N = 1e5 + 10;

struct SQAM {
struct node {
int nx[ALP];
void init() {
memset(nx, 0, sizeof nx);
}
} t[N];
int lst[ALP], pre[N], tot;

void init() {
tot = 1;
t[1].init();
for (int i = 0; i < ALP; ++i) lst[i] = 1;
}

void extend(int c) {
int cur = ++tot;
t[cur].init();
pre[cur] = lst[c];
for (int i = tot - 1; i >= pre[cur]; --i) t[i].nx[c] = cur;
lst[c] = cur;
}
} sqam;

class Solution {
public:
int appendCharacters(string s, string t) {
sqam.init();
for (const char &c : s) {
sqam.extend(c - 'a');
}

int cur = 1;
int n = int(t.size());

for (int i = 0; i < n; i++) {
int c = t[i] - 'a';
if (sqam.t[cur].nx[c]) {
cur = sqam.t[cur].nx[c];
} else {
return n - i;
}
}

return 0;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：head = [5,2,13,3,8]

- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
``````

``````输入：head = [1,1,1,1]

``````

• 给定列表中的节点数目在范围 `[1, 105]`
• `1 <= Node.val <= 105`

You are given the `head` of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the `head` of the modified linked list.

Example 1:

``````Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
``````

Example 2:

``````Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.
``````

Constraints:

• The number of the nodes in the given list is in the range `[1, 105]`.
• `1 <= Node.val <= 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

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

#ifdef LOCAL

struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

#endif

class Solution {
public:
vector<ListNode *> st;

while (!st.empty() && st.back()->val < cur->val) {
st.pop_back();
}
st.push_back(cur);

}

int n = int(st.size());
for (int i = 0; i < n - 1; i++) {
st[i]->next = st[i + 1];
}

return st[0];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 的那个元素。
• 例如，`[2,3,1,4]` 的中位数是 `2``[8,4,3,5,1]` 的中位数是 `4`
• 子数组是数组中的一个连续部分。

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

``````

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

``````

• `n == nums.length`
• `1 <= n <= 105`
• `1 <= nums[i], k <= n`
• `nums` 中的整数互不相同

You are given an array `nums` of size `n` consisting of distinct integers from `1` to `n` and a positive integer `k`.

Return the number of non-empty subarrays in `nums` that have a median equal to `k`.

Note:

• The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element.
• For example, the median of `[2,3,1,4]` is `2`, and the median of `[8,4,3,5,1]` is `4`.
• A subarray is a contiguous part of an array.

Example 1:

``````Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].
``````

Example 2:

``````Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.
``````

Constraints:

• `n == nums.length`
• `1 <= n <= 105`
• `1 <= nums[i], k <= n`
• The integers in `nums` 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:
int countSubarrays(vector<int> &nums, int k) {
int n = int(nums.size());
int target = -1;
for (int i = 0; i < n; i++) {
if (nums[i] < k) {
nums[i] = -1;
} else if (nums[i] > k) {
nums[i] = 1;
} else {
target = i;
}
}

auto mp = map<int, int>();
int cur = 0;
++mp[cur];
for (int i = target + 1; i < n; i++) {
cur += nums[i];
++mp[cur];
}

int res = 0;
cur = 0;
for (int i = target; i >= 0; i--) {
if (i < target) {
cur += nums[i];
}

res += mp[-cur];
res += mp[-cur + 1];
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````