2074D.md (2255B)
1 Source: https://codeforces.com/problemset/problem/2074/D 2 3 D. Counting Points 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 The pink soldiers drew $n$ circles with their center on the $x$-axis of the plane. Also, they have told that the sum of radii is exactly $m$$^{\text{∗}}$. 22 23 Please find the number of integer points inside or on the border of at least one circle. Formally, the problem is defined as follows. 24 25 You are given an integer sequence $x_1,x_2,\ldots,x_n$ and a positive integer sequence $r_1,r_2,\ldots,r_n$, where it is known that $\sum_{i=1}^n r_i = m$. 26 27 You must count the number of integer pairs $(x,y)$ that satisfy the following condition. 28 29 * There exists an index $i$ such that $(x-x_i)^2 + y^2 \le r_i^2$ ($1 \le i \le n$). 30 31 $^{\text{∗}}$Is this information really useful? Don't ask me; I don't really know. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 2\cdot 10^5$). 38 39 The second line of each test case contains $x_1,x_2,\ldots,x_n$ — the centers of the circles ($-10^9 \le x_i \le 10^9$). 40 41 The third line of each test case contains $r_1,r_2,\ldots,r_n$ — the radii of the circles ($1 \le r_i$, $\sum_{i=1}^n r_i = m$). 42 43 It is guaranteed that the sum of $m$ over all test cases does not exceed $2\cdot 10^5$. 44 45 Output 46 47 For each test case, output the number of integer points satisfying the condition on a separate line. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 2 3 57 58 0 0 59 60 1 2 61 62 2 3 63 64 0 2 65 66 1 2 67 68 3 3 69 70 0 2 5 71 72 1 1 1 73 74 4 8 75 76 0 5 10 15 77 78 2 2 2 2 79 ``` 80 81 Output 82 83 ``` 84 13 85 16 86 14 87 52 88 ``` 89 90 Note 91 92 On the first test case, the circle with $r_1=1$ is completely inside the circle with $r_2=2$. Therefore, you only have to count the number of integer points inside the latter. There are $13$ integer points such that $x^2+y^2 \le 2^2$, so the answer is $13$. 93 94 On the second test case, the circle with $r_1=1$ is not completely inside the circle with $r_2=2$. There are $3$ additional points that are inside the first circle but not inside the second circle, so the answer is $3+13=16$.