#PQJ4603x21432. QOJ 4603_21432

    ID: 2975 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2027 互测贪心

QOJ 4603_21432

标题: 经典题 - Problem - QOJ.ac

#21432. 经典题

Statistics

题目描述

有 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

开启了合理的子任务依赖。