AdditionalFile5670.zip

#5670. 「JOI 2026 Final Day3」稻草人 2

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

题目描述

题目译自 JOI 2026 Final Day3 T2 「かかし 2 / Scarecrows 2」

JOI 村有一片广阔的农田。这片农田可以用一个无限延伸的 $xy$ 坐标平面来表示，其中 $x$ 轴的正方向为东，$y$ 轴的正方向为北。

JOI 村的村长为了保护农田免受外敌侵害，打算在田里布置一些稻草人。每个布置好的稻草人根据其位置和朝向，可以守护平面上的特定区域。

目前，村里提出了 $N$ 个布置稻草人的计划，编号为从 $1$ 到 $N$。执行计划 $i$ $(1 \leq i \leq N)$ 所需的代价为 $C_i$，其内容通过整数 $T_i, X_i, Y_i$ 描述如下：

• 如果 $T_i=1$，则在点 $(X_i, Y_i)$ 处放置一个朝向西方的稻草人。该稻草人守护平面上 $x \leq X_i$ 的区域。
• 如果 $T_i=2$，则在点 $(X_i, Y_i)$ 处放置一个朝向东方的稻草人。该稻草人守护平面上 $x \geq X_i$ 的区域。
• 如果 $T_i=3$，则在点 $(X_i, Y_i)$ 处放置一个朝向南方的稻草人。该稻草人守护平面上 $y \leq Y_i$ 的区域。
• 如果 $T_i=4$，则在点 $(X_i, Y_i)$ 处放置一个朝向北方的稻草人。该稻草人守护平面上 $y \geq Y_i$ 的区域。

村长希望从这 $N$ 个计划中选择一部分来执行，使得平面上的每一个点都被至少 $K$ 个稻草人所守护，并希望总代价尽可能小。已知在所有 $N$ 个计划中，放置稻草人的点坐标两两不同。

给定所有布置稻草人计划的信息，请编写一个程序，判定是否可以通过选择部分计划来使平面上的所有点都受到至少 $K$ 个稻草人的守护。如果可行，则计算所需总代价的最小值。

输入格式

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

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

输出格式

输出为了使平面上每个点都被至少 $K$ 个稻草人守护而所需的最小总代价。如果不存在满足条件的计划选择方案，则输出 $-1$。

样例 1

输入

7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

输出

99

例如，如果执行计划 $3$ 和 $5$，稻草人的放置情况如下：

• 在计划 $3$ 中，在点 $(36, 73)$ 处放置一个朝向西方的稻草人。代价为 $78$。
• 在计划 $5$ 中，在点 $(15, 49)$ 处放置一个朝向东方的稻草人。代价为 $21$。

此时，坐标平面上的任何一个点都由至少 $1$ 个稻草人守护。例如，点 $(0, 0)$ 被计划 $3$ 中放置在点 $(36, 73)$ 且面向西方的稻草人守护。此外，总代价为 $78+21=99$。由于不存在总代价更小且能使平面所有点受到至少 $1$ 个稻草人守护的方案，因此输出 $99$。

该样例满足所有子任务的限制。

样例 2

输入

7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

输出

-1

该样例与样例 $1$ 仅在 $K$ 的值上有所不同。

由于无法使坐标平面上的所有点都受到至少 $3$ 个稻草人的守护，因此输出 $-1$。

该样例满足子任务 $3, 4, 5, 6$ 的限制。

样例 3

输入

19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21

输出

315

该样例满足子任务 $3, 4, 5, 6$ 的限制。

样例 4

输入

8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62

输出

328

该样例满足子任务 $3, 4, 5, 6$ 的限制。

数据范围与提示

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

• $1 \leq K \leq N \leq 200000$。
• $T_i$ 为 $1, 2, 3, 4$ 中的一个 $(1 \leq i \leq N)$。
• $0 \leq X_i \leq 10^9$ $(1 \leq i \leq N)$。
• $0 \leq Y_i \leq 10^9$ $(1 \leq i \leq N)$。
• $(X_i, Y_i) \neq (X_j, Y_j)$ $(1 \leq i < j \leq N)$。
• $0 \leq C_i \leq 10^9$ $(1 \leq i \leq N)$。
• 所有输入的值均为整数。

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

子任务	分值	附加限制
$1$	$4$	$K=1$
$2$	$6$	$K \leq 2$
$3$	$11$	$N \leq 500, K \leq 300$
$4$	$27$	$N \leq 6000$
$5$	$19$	$N \leq 75000$
$6$	$33$	无附加限制