← 返回题目列表

AtCoder · joi2026final_g

G. 三角形降雨

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

JOI的国家是一个等边三角形,边长 L 其顶点是点 A, B,和 C。 在这里, L 是正整数。 侧面 AB 连接顶点 A 和 B 东西方向,且顶点 A 是JOI所在国家的最西点,而顶点 B 是最东点。 顶点 C 是JOI国的最北点。

JOI的国家分为 L^2 地区,每个都是边长为等边三角形 1。 作为某个区域的顶点的点称为 格点。 对于整数 x, y 满意 0\leq y\leq L 和 0\leq x\leq L-y,即格点 (1+y)-st 从南方和 (1+x)从西起的 -st 表示为 (x,y)。 特别是, A, B,和 C 表示为 分别是 (0,0), (L,0),和 (0,L)。 例如,下图显示了当 L=5.

在 JOI 的国家, 下一个天气预报 N 天数已公布。 当天 i,预计三角形区域有雨 T_i 其顶点是格点 (X_i, Y_i), (X_i + Z_i, Y_i),和 (X_i, Y_i + Z_i)。 据说某地区预计当天会下雨 i 如果整个区域包含在 T_i.

为了防备降雨造成的灾害,有必要确定每个 k=1,2,\ldots,K,预计至少有降雨的地区数量 k 天。

鉴于 JOI 国家的大小、天气预报和 K,编写一个程序,对于每个 k=1,2,\ldots,K,计算预计至少在 k 天。


输入

输入由标准输入按以下格式给出:

L N K
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

输出

打印 K 行连接到标准输出。 的 k- 第行 (1\leq k\leq K)应包含预计至少在 k 天。


约束

  • 2\leq L\leq 10^9.
  • 2 \leq N \leq 200\,000.
  • 1 \leq K \leq 5.
  • 0\leq X_i\leq L (1\leq i\leq N).
  • 0\leq Y_i\leq L (1\leq i\leq N).
  • 1 \leq Z_i\leq L (1\leq i\leq N).
  • X_i+Y_i+Z_i\leq L (1\leq i\leq N).
  • 所有输入值均为整数。

子任务

  1. (4 点) N = 2, K = 2.
  2. (5 点) L\leq 100, N\leq 100.
  3. (5 点) L\leq 1\,000.
  4. (7 点) N\leq 2\,000.
  5. (10 点) X_i = 0 (1\leq i\leq N), K = 1.
  6. (10 点) X_i = 0 (1\leq i\leq N).
  7. (23 点) K = 1.
  8. (18 点) K \leq 2.
  9. (18 点)没有额外的限制。

示例输入 1

5 2 2
1 0 3
0 1 4

示例输出 1

21
4

如果我们说明每个地区预计会下雨的天数,我们会得到下图。

此示例输入满足子任务的约束 1, 2, 3, 4, 8, 和 9.


示例输入 2

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

示例输出 2

21
10
2
0
0

如果我们说明每个地区预计会下雨的天数,我们会得到下图。

此示例输入满足子任务的约束 2, 3, 4, 和 9.