题号:NC19858
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
- 吾闻夫齐魏徭戍,荆韩召募。万里奔走,连年暴露。沙草晨牧,河冰夜渡。地阔天长,不知归路。寄身锋刃,腷臆谁愬?秦汉而还,多事四夷,中州耗斁,无世无之。古称戎夏,不抗王师。文教失宣,武臣用奇。奇兵有异于仁义,王道迂阔而莫为。呜呼噫嘻!
唐国正在和宋国交战,而你是唐国部队的统帅,你的手下有一些斥候负责刺探情报。
宋国的边境线有n个城市,这些城市从1-n标号,而这些城市分别有一些兵力分布,不妨记为{a1,a2,a3...,an},这些城市的兵力两两不相同(宋国指挥官什么毛病)。
现在你的斥候给了你一些情报,描述宋国的兵力。
但是由于他们只有一些望远镜啥的东西(我也没打过仗我不知道应该有啥子),他们只能目测兵力的位置,对于每个情报,他们都会说三个数l,r,num,表示从l城市到r城市这r-l+1兵力最少的城市有num人的军队。
你的部队很快就要进行战略决战了,但是你发现,斥候中混入了一些奸细,也就是说,他们给你的情报可能是互相矛盾的。
例如,[1,3],100和f[2,3],50矛盾,因为如果2号城市到3号城市的最小兵力是50人,那么1号城市到三号城市的最小兵力不会超过是50人。
你现在明(wu)智(duan)地认(qin)为(ding),越靠前给你汇报情报的斥候,忠诚度越高,也就是说,如果一个斥候的情报与前面某个斥候冲突,那他就是奸细。
现在你需要找出错误的情报,并处斩提供该情报的奸细。
大战在即!你只有2s的时间来处理这个问题。
请注意:每一城市的兵力分布可能是任意数值。如果你认为,斥候们提供的情报没有矛盾,请输出k+1;如果有多个矛盾,请输出第一个与前面情报矛盾的情报。
输入描述:
第一行两个正整数n,k,表示城市和情报的个数。
接下来k行,每行三个正整数l,r,p。
输出描述:
一行一个正整数,表示答案
示例1
输入
复制
100 3
1 70 8
23 30 7
3 5 5
说明
显然,如果第一项成立,[23,30]的最小值应该是8,而不是7。
示例2
输入
复制
9 14
4 4 7
2 2 9
2 5 4
4 7 5
3 3 6
4 6 7
1 1 7
4 7 8
2 5 3
1 3 2
4 5 4
2 4 6
1 4 6
4 7 8
示例3
输入
复制
9 14
4 4 9
2 2 9
2 5 4
4 7 5
3 3 6
4 6 7
1 1 7
4 7 8
2 5 3
1 3 2
4 5 4
2 4 6
1 4 6
4 7 8
说明
对于30%的数据,1<=n,k<=8
对于50%的数据,1<=n,k<=1000
对于100%的数据,1<=n,k<=500000,1<=l<=r<=n,1<=p<=n
备注:
建议使用读入优化:
https://paste.ubuntu.com/p/72Zydvxp3D/
//没错我大括号就是换行,就是Tab缩进。
请注意优化常数
Nowcoder的机子还是挺快的吧,std跑了500多ms