2106D.md (3517B)
1 Source: https://codeforces.com/problemset/problem/2106/D 2 3 D. Flower Boy 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Flower boy has a garden of $n$ flowers that can be represented as an integer sequence $a_1, a_2, \dots, a_n$, where $a_i$ is the beauty of the $i$-th flower from the left. 22 23 Igor wants to collect exactly $m$ flowers. To do so, he will walk the garden from left to right and choose whether to collect the flower at his current position. The $i$-th flower among ones he collects must have a beauty of at least $b_i$. 24 25 Igor noticed that it might be impossible to collect $m$ flowers that satisfy his beauty requirements, so before he starts collecting flowers, he can pick any integer $k$ and use his magic wand to grow a new flower with beauty $k$ and place it anywhere in the garden (between two flowers, before the first flower, or after the last flower). Because his magic abilities are limited, he may do this at most once. 26 27 Output the minimum integer $k$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $m$ flowers. If he can collect $m$ flowers without using the operation, output $0$. If it is impossible to collect $m$ flowers despite using the operation, output $-1$. 28 29 Input 30 31 The first line of the input contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. 32 33 The first line of each test case contains exactly two integers $n$ and $m$ $(1 \le m \le n \le 2 \cdot 10^5)$ — the number of flowers in the garden and the number of flowers Igor wants to collect, respectively. 34 35 The second line of each test case contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ — where $a_i$ is the beauty of the $i$-th flower from the left in the garden. 36 37 The third line of each test case contains $m$ integers $b_1, b_2, ..., b_m$ $(1 \le b_i \le 10^9)$ — where $b_i$ is the minimum beauty the $i$-th flower must have that Igor will collect. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, on a separate line, output the minimum integer $k$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $m$ flowers. If he can collect $m$ flowers without using the operation, output $0$. If it is impossible to collect $m$ flowers despite using the operation, output $-1$. 44 45 Example 46 47 Input 48 49 ``` 50 7 51 52 9 5 53 54 3 5 2 3 3 5 8 1 2 55 56 4 6 2 4 6 57 58 6 3 59 60 1 2 6 8 2 1 61 62 5 4 3 63 64 5 3 65 66 4 3 5 4 3 67 68 7 4 5 69 70 6 3 71 72 8 4 2 1 2 5 73 74 6 1 4 75 76 5 5 77 78 1 2 3 4 5 79 80 5 4 3 2 1 81 82 6 3 83 84 1 2 3 4 5 6 85 86 9 8 7 87 88 5 5 89 90 7 7 6 7 7 91 92 7 7 7 7 7 93 ``` 94 95 Output 96 97 ``` 98 6 99 3 100 7 101 0 102 -1 103 -1 104 7 105 ``` 106 107 Note 108 109 In the first test case, suppose Igor grows a flower of beauty $6$ and places it between the third and the fourth flowers. Then, the garden will look like the following: $[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$. Then, he can select the second, fourth, sixth, seventh, and eighth flowers with beauties $[5, 6, 3, 5, 8]$. 110 111 In the third test case, he can grow a flower of beauty $7$ and place it before the first flower. The garden will look like the following: $[7, 4, 3, 5, 4, 3]$. Now, he can choose the first, second, and fourth flowers. 112 113 In the fourth test case, Igor does not need to use the operation, so the answer is $0$. 114 115 In the sixth test case, no matter how Igor performs the operation, he cannot collect $3$ flowers such that the $i$-th flower he collects has a beauty of at least $b_i$, therefore the answer is $-1$.