No.2520 L1 Explosion
タグ : / 解いたユーザー数 47
作問者 :
MasKoaTS
/ テスター :
fky_
Problem Statement
The wizard Koa is fighting $N$ monsters numbered $1, 2, \dots, N$.
Monster $i$ $(1 \leq i \leq N)$ is located at coordinates $(X_{i}, Y_{i})$ on a two-dimensional plane, and its health is $H_{i}$.
Koa freely chooses one point on the two-dimensional plane and uses Explosion Magic there.
When Explosion Magic is used at coordinates $(x,y)$, for any monster $i$ $(1 \leq i \leq N)$,
its health can be reduced by $d_{i}$.
Here, $d_{i} = \max( M - |x - X_{i}| - |y - Y_{i}|, 0 )$.
For $i = 1,2,\dots,N$ in this order, answer the following question.
On the two-dimensional plane, find the area of the region consisting of the points $(x,y)$ satisfying the following condition, modulo $\mathrm{mod} \ 998244353$.
When Koa uses Explosion Magic at coordinates $(x, y)$, among the $N$ monsters, exactly $i$ of them have health $0$ or less.
Notes
Under the constraints of this problem, it is guaranteed that the area to be found is a rational number.
When it is expressed as an irreducible fraction $p / q$, it is guaranteed that the integer satisfying $p \equiv q \times r \pmod{998244353}$, $r$
$(0 \leq r < 998244353)$, is
uniquely determined, so find this $r$.
Constraints
$1 \leq N \leq 1500$
$2 \leq M \leq 10^{9}$
$-10^{9} \leq X_{i}, Y_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
$1 \leq H_{i} \leq M - 1$ $(1 \leq i \leq N)$
$(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$
All input values are integers.
Input
The input is given in the following format.
$N$ $M$
$X_{1}$ $Y_{1}$ $H_{1}$
$X_{2}$ $Y_{2}$ $H_{2}$
$\vdots$
$X_{N}$ $Y_{N}$ $H_{N}$
Line $1$ contains $N$ and $M$ in this order, separated by a single-byte space.
Line $(1 + i)$ $(1 \leq i \leq N)$ contains $X_{i}, Y_{i}, H_{i}$ in this order, separated by single-byte spaces.
Output
Print the answers, $1$ per line, for a total of $N$ lines.
On line $i$ $(1 \leq i \leq N)$, print the answer to the $i$-th question.
Sample
Sample 1
Input
1 5 0 0 3
Output
8
In question number $1$, the area of the region satisfying the condition is $8$.
For example, when Koa uses Explosion Magic at coordinates $(0,1)$, $$ d_{1} = \max( 5 - | 0 - 0 | - | 1 - 0 |, 0 ) = 4 $$ so the health of monster $1$ can be reduced by $4$, making it $-1 \leq 0$.
Sample 2
Input
3 7 0 -2 5 2 0 4 -1 0 5
Output
499122201 4 499122177
The answers to the questions are $\displaystyle \dfrac{49}{2}, 4, \dfrac{1}{2}$, respectively.
Expressed in $\mathrm{mod} \ 998244353$, these are $499122201, 4, 499122177$, respectively.
Sample 3
Input
5 984744545 -146570235 -7990790 301202754 143580064 67918028 684955441 -43425514 -103157442 445005707 93700695 139883361 763292656 -1577876 104468051 352308994
Output
603011850 593654922 420568561 57524703 424785206
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。