問題一覧 > 通常問題

No.2520 L1 Explosion

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 47
作問者 : MasKoaTS / テスター : Shirotsume fky_
お気に入りにしたユーザー ProblemId : 7709 / 自分の提出
問題文最終更新日: 2023-10-25 00:34:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 410 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。