### Tigutor's blog

By Tigutor, history, 3 years ago, Here is the statement https://wcipeg.com/problem/coi08p3

I found it very interesting, because restrictions are big. I was thinking about using array d[i] — number of cells with distance i to them, but I cannot recalculate it for one rectangle quickly.

So if you have any ideas, please share them  Comments (3)
 » Let $f_i(t)$ be the number of cells covered in the $i$-th sheet after $t$ minutes. It's easy to show that we can split the range $[0, \infty)$ into $O(1)$ ranges such that in each of these ranges, $f_i$ is a constant, linear or quadratic polynomial.What the problem asks is the sum $f(t) = \sum_i f_i(t)$ for various values of $t$. Because each $f_i$ is a piecewise quadratic function with $O(1)$ pieces, $f$ is also a piecewise quadratic function with $O(n)$ pieces. You can calculate the coefficients of the polynomials in each of these pieces (by sweepline, for example) and evaluate a suitable function for each $t$ in the input.
•  » » What would be the formula to calculate covered area for one rectangle? Don’t fully get it
•  » » » If you have a rectangle formed from $(x_1, y_1)$ and $(x_2, y_2)$ (here, I use them as points, not unit cells like in the problem), then the area covered at time $t$ is $\max(0, \min(t, x_2) - \max(-t, x_1)) \cdot \max(0, \min(t, y_2) - \max(-t, y_1)).$