2193F.md (2560B)
1 Source: https://codeforces.com/problemset/problem/2193/F 2 3 F. Pizza Delivery 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 Courier YF has earned the title of the best pizza delivery person GR. The manager does not like him, so he decided to give him a very difficult task. The manager provided him with $n$ coordinates of houses $(x_i, y_i)$ where he needs to deliver the pizza. He will deliver the pizza in the following way: 22 23 * GR pizza is prepared at the point ($Ax, Ay$) and YF starts the delivery from this point. 24 * To deliver the pizza, he can move from the point ($x, y$) to three points ($x+1, y$), ($x, y+1$), ($x, y-1$). 25 * After he has delivered all the pizzas, he returns home to the point ($Bx, By$). 26 27 Each move takes him exactly one second, and handing over the pizza to the customer takes $0$ seconds. The manager wants the delivery to be as fast as possible. You need to find the minimum delivery time for all GR pizzas. It is guaranteed that delivery is always possible. 28 29 Input 30 31 Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 32 33 The first line of each test case contains five integers $n$, $Ax$, $Ay$, $Bx$, $By$ ($1 \le n \le 2 \cdot 10^5$, $1 \le Ax, Ay, Bx, By \le 10^9$) — the number of houses for delivery, as well as the coordinates of the start and end points. 34 35 The second line of each test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($Ax \lt x_i \lt Bx$). 36 37 The third line of each test case contains $n$ integers $y_1, y_2, \dots, y_n$ ($1 \le y_i \le 10^9$). 38 39 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer on a separate line — the minimum time required for pizza delivery. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 1 2 3 5 2 53 54 4 55 56 4 57 58 3 1 3 5 2 59 60 3 4 3 61 62 5 4 1 63 64 6 1 2 7 3 65 66 5 2 3 5 5 3 67 68 6 4 3 1 4 1 69 70 5 6 9 8 6 71 72 7 7 7 7 7 73 74 3 1 8 8 3 75 ``` 76 77 Output 78 79 ``` 80 6 81 82 13 83 84 19 85 86 15 87 ``` 88 89 Note 90 91 Consider the second test case: 92 93 * Move from the point ($Ax, Ay$) to the point ($x_3, y_3$) in $4$ seconds. 94 * Move from the point ($x_3, y_3$) to the point ($x_1, y_1$) in $4$ seconds. 95 * Move from the point ($x_1, y_1$) to the point ($x_2, y_2$) in $2$ seconds. 96 * Move from the point ($x_2, y_2$) to the point ($Bx, By$) in $3$ seconds. 97 98 In total, the delivery takes $4 + 4 + 2 + 3 = 13$ seconds. It can be proven that it is impossible to deliver the pizza faster.