AdditionalFile5669.zip

#5669. 「JOI 2026 Final Day3」三角形降雨

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day3 T1 「三角形降雨 / Triangular Rainfall」

JOI 国是一个以点 $A, B, C$ 为顶点，边长为 $L$ 的正三角形。这里 $L$ 是正整数。边 $AB$ 将顶点 $A, B$ 在东西方向上连接，顶点 $A$ 是 JOI 国的最西端，顶点 $B$ 是 JOI 国的最东端。顶点 $C$ 是 JOI 国的最北端。

JOI 国被划分为 $L^2$ 个边长为 $1$ 的正三角形区域。若一个点是某个区域的顶点，则称该点为格子点。对于满足 $0 \le y \le L$ 且 $0 \le x \le L-y$ 的整数 $x, y$，从南侧起第 $1+y$ 个、从西侧起第 $1+x$ 个格子点表示为 $(x, y)$。特别地，$A$ 表示为 $(0, 0)$，$B$ 表示为 $(L, 0)$，$C$ 表示为 $(0, L)$。例如，下图表示了 $L=5$ 时的区域和格子点。

JOI 国发布了接下来 $N$ 天的天气预报。第 $i$ 天，预报称以格子点 $(X_i, Y_i), (X_i+Z_i, Y_i), (X_i, Y_i+Z_i)$ 为顶点的正三角形区域 $T_i$ 将会降雨。所谓第 $i$ 天预报有雨的区域，是指该区域整体都包含在 $T_i$ 之内的单位三角形区域。

为了防范降雨造成的灾害，对于 $k=1, 2, \ldots, K$，需要调查预报有 $k$ 天以上降雨的区域数量。

给定 JOI 国的大小、天气预报信息以及 $K$，请编写一个程序，求出对于 $k=1, 2, \ldots, K$，预报有 $k$ 天以上降雨的区域数量。

输入格式

第一行包含三个整数 $L, N, K$。

接下来的 $N$ 行，其中第 $i$ 行包含三个整数 $X_i, Y_i, Z_i$。

输出格式

标准输出输出 $K$ 行。第 $k$ 行 $(1 \le k \le K)$ 输出预报有 $k$ 天以上降雨的区域数量。

样例 1

输入

5 2 2
1 0 3
0 1 4

输出

21
4

对于每个区域，预报有雨的天数图示如下：

此样例满足子任务 $1, 2, 3, 4, 8, 9$ 的限制。

样例 2

输入

5 4 5
1 0 4
0 1 3
2 0 2
1 2 2

输出

21
10
2
0
0

对于每个区域，预报有雨的天数图示如下：

此样例满足子任务 $2, 3, 4, 9$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \le L \le 10^9$。
• $2 \le N \le 200000$。
• $1 \le K \le 5$。
• $0 \le X_i \le L$ $(1 \le i \le N)$。
• $0 \le Y_i \le L$ $(1 \le i \le N)$。
• $1 \le Z_i \le L$ $(1 \le i \le N)$。
• $X_i + Y_i + Z_i \le L$ $(1 \le i \le N)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。