#1993. 经典题

    ID: 1993 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4603来源:qoj.ac数据:公开样例二分答案

经典题

经典题

题目描述

标题: 经典题 - 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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
1 2 1
1 2 1
2 3 2
1