2257D.md (2734B)
1 Source: https://codeforces.com/problemset/problem/2257/D 2 3 D. Bermuda Rectangle 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 Beaver is swimming across the ocean (yes, he can do that). Here, it aims to explore the Bermuda Rectangle. Of course, it poses no danger to The Beaver, but it is interesting from a scientific perspective. 22 23 Unlike the Bermuda Triangle, not much is known about the Bermuda Rectangle. Specifically, The Beaver knows for sure that the area of the rectangle is $S$, its sides are integers, and the bottom left corner is located at the point $(0, 0)$. 24 25 The Beaver is interested in how many cells from a rectangle with sides $x$ and $y$, whose bottom left corner is at the point $(0, 0)$, can be located within the Bermuda Rectangle. A cell is considered to be within the Bermuda Rectangle if there exists a rectangle that satisfies the given constraints of the Bermuda Rectangle and contains that cell. Help The Beaver quickly respond to queries! You need to answer $q$ such queries. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows. 30 31 The first line of each test case contains two integers $S$ and $q$ — the area of the Bermuda Rectangle and the number of queries ($1 \le S \le 10^{14}$; $1 \le q \le 3 \cdot 10^5$). 32 33 This is followed by $q$ lines, each containing two integers $x, y$ — the next query ($1 \le x, y \le S$). 34 35 It's guaranteed that the sum of $q$ over all test cases doesn't exceed $3 \cdot 10^5$. 36 37 It's guaranteed that the sum of $\sqrt{S}$ over all test cases doesn't exceed $10^7$. 38 39 Output 40 41 For each query, output a single integer on a separate line — the answer to the query. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 6 4 51 52 2 3 53 54 4 5 55 56 6 6 57 58 1 1 59 60 5 2 61 62 2 2 63 64 3 4 65 66 8 2 67 68 3 1 69 70 5 6 71 ``` 72 73 Output 74 75 ``` 76 6 77 78 11 79 80 14 81 82 1 83 84 3 85 86 6 87 88 3 89 90 15 91 ``` 92 93 Note 94 95 In the first test case, every cell of the rectangle $(2, 3)$ is counted in the first query, since this rectangle itself can be the Bermuda Rectangle. 96 97 The second query of the first test case is illustrated in the figure. The answer to the query is the number of cells in the intersection of the blue and red shapes. 98 99  4 blue rectangles — possible positions of the Bermuda Rectangle. Red — the rectangle of the query $(x, y) = (4, 5)$ 100 101 In the third query of the first test case, every cell that can lie in at least one possible Bermuda Rectangle is counted. 102 103 In the fourth query of the first test case, the only cell of the query rectangle can lie in the Bermuda Rectangle, so the answer is $1$.