/ OIer TK / 题库 /

序列判定

序列判定

测试数据来自 system/1671

背景

做题目前,讲一个寓言。

有一对兄弟,他们的家住在80层楼上。有一天他们外出旅行回家,发现大楼停电了!虽然他们背着大包的行李,但看来没有什么别的选择,于是哥哥对弟弟说,我们就爬楼梯上去!于是,他们背着两大包行李开始爬楼梯。爬到20楼的时候他们开始累了,哥哥说“包包太重了,不如这样吧,我们把包包放在这里,等来电后坐电梯来拿。”于是,他们把行李放在了20楼,轻松多了,继续向上爬。

他们有说有笑地往上爬,但是好景不长,到了40楼,两人实在累了。想到还只爬了一半,两人开始互相埋怨,指责对方不注意大楼的停电公告,才会落得如此下常他们边吵边爬,就这样一路爬到了60楼。到了60楼,他们累得连吵架的力气也没有了。弟弟对哥哥说,“我们不要吵了,爬完它吧。”于是他们默默地继续爬楼,终于80楼到了!兴奋地来到家门口兄弟俩才发现他们的钥匙留在了20楼的包包里了。

下面开始做题。

描述

给出M个三元组(a,b,c),表示a~b中最小值为c.
找出最小的I满足:存在N长序列满足1~I-1中所有的三元组的要求,并且不存在N长序列满足1~I中所有的三元组的要求,若存在N长序列满足所有三元组要求,输出0。

格式

输入格式

第一行两个整数n,m
接下来m行,每行一个三元组(a,b,c);
保证1<=n<=10^6 0<=m<=50000 a<=b a+500>=b 0<=c<=n

输出格式

一个数,如题

样例1

样例输入1

20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出1

3

限制

各个测试点1s

提示

From usaco 2008.

信息

ID
1618
难度
(无)
分类
数据结构 | 其他 | 二分查找 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者