No.2229 Treasure Searching Rod (Hard)
タグ : / 解いたユーザー数 103
作問者 : 👑
akakimidori
This problem has the same setting as "Treasure Searching Rod (Easy)"; only the constraints differ.
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell in row $i$ and column $j$ is denoted by $(i,j)$.
In $K$ cells of this grid, $10^{100}$ "treasures" are placed in each. The $k$-th treasure is in cell $(x_k, y_k)$, and its value per $1$ piece is $v_k$.
Now, we call the operation described below "the operation on cell $(i,j)$".
For each cell $(x,y)$ that satisfies all of the following conditions with respect to cell $(i,j)$, if it has treasure, obtain $1$ piece of the treasure in cell $(x,y)$.
- $x + y \geq i + j$
- $x - y \geq i - j$
You performed the operation $1$ time on every cell $(i,j)$ satisfying $1 \leq i \leq H, 1 \leq j \leq W$. Find the total value of the treasures obtained, modulo $998244353$.
Constraints
- All input values are integers.
- $1 \leq H,W \leq 10^5$
- $0 \leq K \leq \min(HW, 2 \times 10^5)$
- $1 \leq x_k \leq H$
- $1 \leq y_k \leq W$
- $0 \leq v_k \leq 10^9$
- $(x_k, y_k) \neq (x_l, y_l) (k \neq l)$
Input
The input is given from standard input in the following format.
$H$ $W$ $K$ $x_1$ $y_1$ $v_1$ $x_2$ $y_2$ $v_2$ $\vdots$ $x_K$ $y_K$ $v_K$
Output
Output the total value of the treasures obtained, modulo $998244353$.
Sample
Sample 1
Input
3 3 4 1 2 4 2 1 5 2 2 6 3 1 2
Output
55
The grid and the values of the treasures placed on it are as shown in the following figure.
For example, the range from which treasures can be obtained by the operation on cell $(1,2)$ is shown below.
- The value of the treasures obtained by the operation on cell $(1,1)$ is $5+6+2=13$.
- The value of the treasures obtained by the operation on cell $(1,2)$ is $4+5+6+2=17$.
- The value of the treasures obtained by the operation on cell $(1,3)$ is $6+2=8$.
- The value of the treasures obtained by the operation on cell $(2,1)$ is $5+2=7$.
- The value of the treasures obtained by the operation on cell $(2,2)$ is $6+2=8$.
- No treasure is obtained by the operation on cell $(2,3)$.
- The value of the treasures obtained by the operation on cell $(3,1)$ is $2$.
- No treasure is obtained by the operation on cell $(3,2)$.
- No treasure is obtained by the operation on cell $(3,3)$.
Therefore, the total value of the treasures obtained is $13+17+8+7+8+2=55$.
Sample 2
Sample 3
Input
2 3 2 1 2 1000000000 2 3 1000000000
Output
7022588
Output the total value of the treasures modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
