← 返回题目列表

AtCoder · joi2026final_h

H. 稻草人 2

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

分数: 100 点

问题陈述

JOI村有一片广阔的田野。 场用无穷大来表示 xy- 平面,其中正方向 x- 轴为东且正方向 y- 轴为北。

JOI村村长计划在田野里放置几个稻草人,以保护村子免受敌人的侵害。 每个稻草人根据其位置和方向保护平面的特定区域。

目前, N 安置计划已提出,编号为 1 to N。 执行计划 i (1 \leq i \leq N) 需要成本 C_i。 每个计划由三个整数描述 T_i, X_i, Y_i 如下。

  • If T_i = 1,在该点放置一个稻草人 (X_i, Y_i) 面向西。 这个稻草人保护平面上的所有点满足 x \leq X_i.
  • If T_i = 2,在该点放置一个稻草人 (X_i, Y_i) 面向东。 这个稻草人保护平面上的所有点满足 x \geq X_i.
  • If T_i = 3,在该点放置一个稻草人 (X_i, Y_i) 朝南。 这个稻草人保护平面上的所有点满足 y \leq Y_i.
  • If T_i = 4,在该点放置一个稻草人 (X_i, Y_i) 朝北。 这个稻草人保护平面上的所有点满足 y \geq Y_i.

市长想要选择并执行其中一些 N 计划使平面上的每个点至少受到保护 K 稻草人。 在所有这些选择中,总成本应该最小化。 保证坐标 (X_i, Y_i) 之间成对不同 N 计划。

鉴于信息 N 计划,确定是否可以选择计划使得平面上的每个点至少受到保护 K 稻草人。 如果可能,输出所选计划的最小可能总成本。


输入

从标准输入读取以下数据。

N K
T_1 X_1 Y_1 C_1
T_2 X_2 Y_2 C_2
\vdots
T_{N} X_{N} Y_{N} C_{N}

输出

输出所需的最小总成本,使得平面上的每个点至少受到保护 K 稻草人。 如果没有办法选择满足条件的计划,则输出 -1.


约束

  • 1 \leq K \leq N \leq 200\,000.
  • T_i 是其中之一 1, 2, 3, or 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 6\,000.
  5. (19 点) N \leq 75\,000.
  6. (33 点)没有额外的限制。

示例输入 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

示例输出 1

99

例如,假设计划 3 和 5 被执行。 然后稻草人的放置方式如下。

  • 计划中 3,在该点放置一个稻草人 (36,73) 面向西。 成本是 78.
  • 计划中 5,在该点放置一个稻草人 (15,49) 面向东。 成本是 21.

在这种情况下,坐标平面上的每个点都被至少一个稻草人保护。 例如,点 (0,0) 受到放置在的稻草人的保护 (36,73) 计划面向西 3。 总成本是 78 + 21 = 99。 用至少一个稻草人以较小的总成本保护平面上的每个点是不可能的,所以输出应该是 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

示例输出 2

-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

示例输出 3

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

示例输出 4

328

此示例输入满足子任务的约束 3,4,5,6.