Neutral Tonality (Codeforces 1893B)
Tags: Greedy, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers, as well as an array $$$b$$$ consisting of $$$m$$$ integers.Let $$$\text{LIS}(c)$$$ denote the length of the longest increasing subsequence of array $$$c$$$. For example, $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$, $$$\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$$$ = $$$3$$$, $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.You need to insert the numbers $$$b_1, b_2, \ldots, b_m$$$ into the array $$$a$$$, at any positions, in any order. Let the resulting array be $$$c_1, c_2, \ldots, c_{n+m}$$$. You need to choose the positions for insertion in order to minimize $$$\text{LIS}(c)$$$.Formally, you need to find an array $$$c_1, c_2, \ldots, c_{n+m}$$$ that simultaneously satisfies the following conditions: The array $$$a_1, a_2, \ldots, a_n$$$ is a subsequence of the array $$$c_1, c_2, \ldots, c_{n+m}$$$. The array $$$c_1, c_2, \ldots, c_{n+m}$$$ consists of the numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$$$, possibly rearranged. The value of $$$\text{LIS}(c)$$$ is the minimum possible among all suitable arrays $$$c$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n, m$$$ $$$(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$$$ — the length of array $$$a$$$ and the length of array $$$b$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ $$$(1 \leq b_i \leq 10^9)$$$ — the elements of the array $$$b$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output $$$n + m$$$ numbers — the elements of the final array $$$c_1, c_2, \ldots, c_{n+m}$$$, obtained after the insertion, such that the value of $$$\text{LIS}(c)$$$ is minimized. If there are several answers, you can output any of them.

Note: In the first test case, $$$\text{LIS}(a) = \text{LIS}([6, 4]) = 1$$$. We can insert the number $$$5$$$ between $$$6$$$ and $$$4$$$, then $$$\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$$$.In the second test case, $$$\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$$$ = $$$4$$$. After the insertion, $$$c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$$$. It is easy to see that $$$\text{LIS}(c) = 4$$$. It can be shown that it is impossible to achieve $$$\text{LIS}(c)$$$ less than $$$4$$$.

Sample Inputs:
7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777

Sample Outputs:
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

Solution (Python):
import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = sorted(map(int, input().split()))
    c = []
    for x in a:
        while b and b[-1] >= x:
            c.append(b.pop())
        c.append(x)
    c.extend(b[::-1])
    print(*c)

Solution (Python):
def InputList(Dtype=int):
    return list(map(Dtype, input().split()))
for _ in range(int(input())):
    (N, M) = InputList()
    a = InputList()
    b = InputList()
    b.sort()
    res = []
    for n in a:
        while b and b[-1] >= n:
            res.append(b.pop())
        res.append(n)
    b.reverse()
    res += list(b)
    print(*res)

Solution (Python):
for t in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    b.sort()
    ans = []
    for i in a:
        while b and b[-1] >= i:
            ans.append(b.pop())
        ans.append(i)
    print(*ans, *reversed(b))