1971E.md (3082B)
1 Source: https://codeforces.com/problemset/problem/1971/E 2 3 E. Find the Car 4 5 time limit per test 6 7 3 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 Timur is in a car traveling on the number line from point $0$ to point $n$. The car starts moving from point $0$ at minute $0$. 22 23 There are $k+1$ signs on the line at points $0, a_1, a_2, \dots, a_k$, and Timur knows that the car will arrive there at minutes $0, b_1, b_2, \dots, b_k$, respectively. The sequences $a$ and $b$ are strictly increasing with $a_k = n$. 24 25  26 27 Between any two adjacent signs, the car travels with a constant speed. Timur has $q$ queries: each query will be an integer $d$, and Timur wants you to output how many minutes it takes the car to reach point $d$, rounded down to the nearest integer. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 The first line of each test case contains three integers $n$, $k$, and $q$, ($k \leq n \leq 10^9$; $1 \leq k, q \leq 10^5$) — the final destination, the number of points Timur knows the time for, and the number of queries respectively. 34 35 The second line of each test case contains $k$ integers $a_i$ ($1 \leq a_i \leq n$; $a_i \lt a_{i+1}$ for every $1 \leq i \leq k-1$; $a_k = n$). 36 37 The third line of each test case contains $k$ integers $b_i$ ($1 \leq b_i \leq 10^9$; $b_i \lt b_{i+1}$ for every $1 \leq i \leq k-1$). 38 39 Each of the following $q$ lines contains a single integer $d$ ($0 \leq d \leq n$) — the distance that Timur asks the minutes passed for. 40 41 The sum of $k$ over all test cases doesn't exceed $10^5$, and the sum of $q$ over all test cases doesn't exceed $10^5$. 42 43 Output 44 45 For each query, output a single integer — the number of minutes passed until the car reaches the point $d$, rounded down. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 10 1 3 55 56 10 57 58 10 59 60 0 61 62 6 63 64 7 65 66 10 2 4 67 68 4 10 69 70 4 7 71 72 6 73 74 4 75 76 2 77 78 7 79 80 1000000000 1 1 81 82 1000000000 83 84 1000000000 85 86 99999999 87 88 6 1 3 89 90 6 91 92 5 93 94 2 95 96 6 97 98 5 99 ``` 100 101 Output 102 103 ``` 104 0 6 7 105 5 4 2 5 106 99999999 107 1 5 4 108 ``` 109 110 Note 111 112 For the first test case, the car goes from point $0$ to point $10$ in $10$ minutes, so the speed is $1$ unit per minute and: 113 114 * At point $0$, the time will be $0$ minutes. 115 * At point $6$, the time will be $6$ minutes. 116 * At point $7$, the time will be $7$ minutes. 117 118 For the second test case, between points $0$ and $4$, the car travels at a speed of $1$ unit per minute and between $4$ and $10$ with a speed of $2$ units per minute and: 119 120 * At point $6$, the time will be $5$ minutes. 121 * At point $4$, the time will be $4$ minutes. 122 * At point $2$, the time will be $2$ minutes. 123 * At point $7$, the time will be $5.5$ minutes, so the answer is $5$. 124 125 For the fourth test case, the car travels with $1.2$ units per minute, so the answers to the queries are: 126 127 * At point $2$, the time will be $1.66\dots$ minutes, so the answer is $1$. 128 * At point $6$, the time will be $5$ minutes. 129 * At point $5$, the time will be $4.16\dots$ minutes, so the answer is $4$.