/ Vijos / 题库 /

区间

区间

描述

对于一个整数序列,给出的一个三元组[a,b,c]表示该序列在闭区间[a,b]的整数至少有c个,其中a,b,c均为整数。

题目将给出n个三元组,求同时满足这n个三元组的序列的最少元素个数是多少。如果不存在这样的满足要求的序列,则输出-1。

格式

输入格式

第一行一个整数n(n<=50000),表示区间个数。

接下来n行,每行三个整数a,b,c(0<=a<=b<=50000,1<=c<=b-a+1),用一个空格隔开,意义如题目描述。

输出格式

一个数,即为答案

样例1

样例输入1

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

样例输出1

6

限制

每个测试点1s

提示

由于官方数据不全,所以有几个点是自己做的
样例说明:
满足条件的最少元素序列:3,4,5,8,9,10
[3,7]中有3,4,5三个数
[8,10]中有8,9,10三个数
……

来源

zju

信息

ID
1532
难度
7
分类
图结构 | 差分约束贪心 点击显示
标签
(无)
递交数
1736
已通过
285
通过率
16%
被复制
1
上传者

相关

在下列训练计划中:

noip进阶班2017训练

RP++分类题库