P4800 [CEOI 2015] Nuclear Country (Day2)

Nuclear Country can be seen as a rectangle made of a $W \times H$ grid of cells. There are $N$ nuclear power plants in Nuclear Country, and each plant occupies one cell. Unfortunately, Nuclear Country has suffered a once-in-a-century major earthquake, causing all nuclear power plants to leak radiation. The leakage level of each nuclear power plant can be described by two integers $a, b$. If the plant at $P=[x_P,y_P]$ explodes, then a cell $C=[x_C,y_C]$ will receive an additional $\mathrm{max}(0,$ $a-b\times d(P,C))$ becquerels of radiation (becquerel is a unit), where $d(P,C)$ is the Chebyshev distance between the two cells, i.e. $d(P,C) =$ $\mathrm{max}(|x_P - x_C|,$ $|y_P - y_C|)$. A cell may be affected by radiation leaks from multiple plants. For example, if a plant with $a = 7,$ $b = 3$ explodes, the cell $X$ where it is located will receive $7$ becquerels of radiation. The $8$ cells $Y$ with $d(X,Y) = 1$ will receive $4$ becquerels, and the $16$ cells $Z$ with $d(X,Z) = 2$ will receive $1$ becquerel. The environmental agency gives you $Q$ queries. Each query specifies a rectangle within Nuclear Country. You need to answer: what is the average radiation received (per cell) within that rectangular area.

The first line contains two positive integers $W$ and $H$ $(W \times H \leq 2.5\times 10^6)$, representing the width and height of Nuclear Country. The second line contains one positive integer $N$, the number of nuclear power plants $(1 \leq N \leq 2\times 10^5)$. In the next $N$ lines, each line contains four positive integers $x_i,y_i,a_i,b_i$ $(1 \leq x_i \leq W, 1 \leq y_i \leq H, 1 \leq a_i,b_i \leq 10^9)$, meaning there is a plant at cell $[x_i,y_i]$ with parameters $a_i$ and $b_i$. Each cell contains at most one plant. Line $N+3$ contains one positive integer $Q$, the number of queries $(1 \leq Q \leq 2\times 10^5)$. In the next $Q$ lines, each line contains four positive integers $x_{1j},y_{1j},x_{2j},y_{2j}$ $(1 \leq x_{1j} \leq x_{2j} \leq W, 1 \leq y_{1j} \leq y_{2j} \leq H)$, describing a query rectangle whose top-left corner is $[x_{1j},y_{1j}]$ and whose bottom-right corner is $[x_{2j},y_{2j}]$. You may assume that the total radiation within Nuclear Country is less than $2^{63}$.

For each query, output one line with the average radiation over all cells in the given rectangle, rounded to the nearest integer.

The following shows the radiation in each cell after two explosions: ```plain 7 6 3 2 4 6 5 2 1 3 3 2 ``` - The total radiation in a $2^2$ square area is $14$, so the average is $14\div 4=3.5$, which rounds to $4$. - The total radiation in the whole Nuclear Country is $44$, so the average is $44\div 12 \approx 3.67$, which rounds to $4$. - For a single cell, the average radiation is exactly the radiation it receives. - For the last row, the average is $9\div 4=2.25$, which rounds to $2$. There are 14 test cases. The odd-numbered test cases contain only plants where $a$ is a multiple of $b$. Further limits for each subtask are as follows: |Test case|Additional constraints|Score| |:-:|:-:|:-:| |$1$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$3$| |$2$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$2$| |$3$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$3$| |$4$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$2$| |$5$|$H=1,N\cdot W \leq 10^8$|$6$| |$6$|$H=1,N\cdot W \leq 10^8$|$4$| |$7$|$N\cdot W \cdot H \leq 10^8$|$6$| |$8$|$N\cdot W \cdot H \leq 10^8$|$4$| |$9$|$H=1$|$15$| |$10$|$H=1$|$10$| |$11$|There are no explosion events that satisfy the definition of **boundary**|$15$| |$12$|There are no explosion events that satisfy the definition of **boundary**|$10$| |$13$|None|$12$| |$14$|None|$8$| If a nuclear power plant is on the border of Nuclear Country, or close to the border, its explosion may also affect cells outside Nuclear Country. An explosion that affects cells outside Nuclear Country is called a **boundary**. Translated by ChatGPT 5