2106C.md (2439B)
1 Source: https://codeforces.com/problemset/problem/2106/C 2 3 C. Cherry Bomb 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 Two integer arrays $a$ and $b$ of size $n$ are complementary if there exists an integer $x$ such that $a_i + b_i = x$ over all $1 \le i \le n$. For example, the arrays $a = [2, 1, 4]$ and $b = [3, 4, 1]$ are complementary, since $a_i + b_i = 5$ over all $1 \le i \le 3$. However, the arrays $a = [1, 3]$ and $b = [2, 1]$ are not complementary. 22 23 Cow the Nerd thinks everybody is interested in math, so he gave Cherry Bomb two integer arrays $a$ and $b$. It is known that $a$ and $b$ both contain $n$ non-negative integers not greater than $k$. 24 25 Unfortunately, Cherry Bomb has lost some elements in $b$. Lost elements in $b$ are denoted with $-1$. Help Cherry Bomb count the number of possible arrays $b$ such that: 26 27 * $a$ and $b$ are complementary. 28 * All lost elements are replaced with non-negative integers no more than $k$. 29 30 Input 31 32 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) — the size of the arrays and the maximum possible value of their elements. 35 36 The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($0 \le a_i \le k$). 37 38 The third line contains $n$ integers $b_1, b_2, ..., b_n$ ($-1 \le b_i \le k$). If $b_i = -1$, then this element is missing. 39 40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 41 42 Output 43 44 Output exactly one integer, the number of ways Cherry Bomb can fill in the missing elements from $b$ such that $a$ and $b$ are complementary. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 3 10 54 55 1 3 2 56 57 -1 -1 1 58 59 5 1 60 61 0 1 0 0 1 62 63 -1 0 1 0 -1 64 65 5 1 66 67 0 1 0 0 1 68 69 -1 1 -1 1 -1 70 71 5 10 72 73 1 3 2 5 4 74 75 -1 -1 -1 -1 -1 76 77 5 4 78 79 1 3 2 1 3 80 81 1 -1 -1 1 -1 82 83 5 4 84 85 1 3 2 1 3 86 87 2 -1 -1 2 0 88 89 5 5 90 91 5 0 5 4 3 92 93 5 -1 -1 -1 -1 94 ``` 95 96 Output 97 98 ``` 99 1 100 0 101 0 102 7 103 0 104 1 105 0 106 ``` 107 108 Note 109 110 In the first example, the only way to fill in the missing elements in $b$ such that $a$ and $b$ are complementary is if $b = [2, 0, 1]$. 111 112 In the second example, there is no way to fill in the missing elements of $b$ such that $a$ and $b$ are complementary. 113 114 In the fourth example, some $b$ arrays that are complementary to $a$ are: $[4, 2, 3, 0, 1], [7, 5, 6, 3, 4],$ and $[9, 7, 8, 5, 6]$.