#P4388. JOI2012 invitation

    ID: 3591 传统题 1000ms 512MiB 尝试: 72 已通过: 21 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理离散化图论最小生成树候选边稀疏化Kruskal数据结构普通并查集路径压缩CF2500

JOI2012 invitation

[JOI 2012 春季合宿] Invitation 招待

题目描述

JOI 镇要开一场聚会。镇上有 AA 只狗,编号为 11 至 AA,还有 BB 只猫,编号为 11 至 BB。你想邀请它们全都来参加。

共有 NN 个好友小组。第 ii 组包含编号从 PiP_i 到 QiQ_i 的所有狗,以及编号从 RiR_i 到 SiS_i 的所有猫,友好度为 TiT_i。一只动物可以属于多个小组,也可以不属于任何小组。

编号为 CC 的狗已经受邀,不计幸福值。其余动物按以下规则邀请:

  1. 对每只尚未受邀的动物,查看它所属且已有至少一位成员受邀的所有小组。它这一轮的幸福值等于这些组中最高的友好度;若没有这样的组,幸福值为 00。
  2. 邀请幸福值最高的一只。平局时狗优先于猫;种类也相同时,编号较小者优先。
  3. 如果所选动物的幸福值为 00,邀请失败。否则邀请这只动物并计入它此时的幸福值。若还有动物没受邀,重新计算下一轮。

判断能否邀请全部动物;如果可以,求所计入的幸福值之和。

输入格式

第一行三个整数 A,B,CA,B,C,其中 1≤A,B≤1091\le A,B\le10^9、1≤C≤A1\le C\le A。

第二行一个整数 NN(1≤N≤1051\le N\le10^5)。

接下来 NN 行,第 ii 行为 Pi,Qi,Ri,Si,TiP_i,Q_i,R_i,S_i,T_i,满足 1≤Pi≤Qi≤A1\le P_i\le Q_i\le A、1≤Ri≤Si≤B1\le R_i\le S_i\le B、1≤Ti≤1091\le T_i\le10^9。两个编号区间都包含端点。

输出格式

输出一行一个整数:若能邀请所有动物,输出各轮计入的幸福值之和;否则输出 −1-1。

样例 #1

样例输入 #1

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

样例输出 #1

280

最初只有狗 3 受邀。第一轮,狗 2、狗 4、猫 1、猫 2 和猫 3 的幸福值都为 2020,所以先邀请狗 2。下一轮狗 1、猫 2、猫 3 和猫 4 的幸福值都为 4040,所以邀请狗 1。完整顺序如下:

动物 编号 幸福值
狗 3 —
2 20
1 40
猫 2
3
4
狗 30
5
猫 1 20
5 10
6

总幸福值为 280280。

样例 #2

样例输入 #2

10 10 1
2
1 5 1 5 3
6 10 6 10 4

样例输出 #2

-1

邀请了编号 11 至 55 的狗和猫后,其余动物的幸福值都是 00。按平局规则选到狗 6,此时邀请失败。

提示

原赛 30% 的分值满足 A,B≤1000A,B\le1000 且 N≤2000N\le2000;原赛 50% 的分值满足 N≤2000N\le2000。