codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/2fe6586a697f51a9e3ce25327c898506ceeb098c.png) 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$.