#PQJ4603x21432. QOJ 4603_21432
QOJ 4603_21432
标题: 经典题 - Problem - QOJ.ac
#21432. 经典题
题目描述
有 n 个任务,任务 i 需要占用 [li,ri] 中的一个格子,如果占用的格子编号 ≤ti,则额外获得 1 奖励,求所有任务都完成的情况下能获得的最大奖励。
输入格式
一行两个整数 n,m,分别是任务的数量和格子数量。
接下来 n 行,一行三个整数 l,r,t 表示一个任务。
输出格式
如果无法完成所有任务,输出 −1,否则输出答案。
样例 #1
输入
3 3
1 2 1
1 2 1
2 3 2
输出
1
样例解释
将任务依次分配给 1,2,3 格子,可知有一个任务能获得奖励。
数据范围
对于所有数据,满足 1≤n,m≤5×105,1≤li≤ti≤ri≤m。
子任务 分值 特殊限制 1 3 n,m≤15 2 12 所有 li 相等 3 3 所有 ti 相等 4 19 n,m≤500 5 20 n,m≤2000 6 21 n,m≤105 7 22 n,m≤5×105
开启了合理的子任务依赖。