Skip to content

11586: 【原1586】Dog

题目

题目描述

author: Blacko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1586

Description

隔壁村的阿黑的Dog没有跑, 但Dog已经15岁了, 相当于人类达到了79岁.

为了防止Dog患上犬类认知障碍 (Canine cognitive dysfunction, CCD), 阿黑决定陪Dog玩猜数游戏.

游戏开始前,阿黑会在Dog后面摆上N个数字. 所有数字排成一条直线,按次序从1N编号.

游戏开始后,Dog将会询问阿黑Q个问题,每个问题的格式都是一样的:

"位置在lr的数字中,最小的数字是多少?"

对每个问题,阿黑都会回答一个数字A. 但阿黑的回答可能不正确.

年迈的Dog想知道阿黑从哪里开始已经出现了矛盾, 可惜的是, Dog其实已经患上了严重的犬类认知障碍, 于是这就成了一道机考题.

Input Format

输入的第一行有两个用空格分开的整数NQ, 含义如上.

接下来Q行, 每行有三个用空格分开的整数l, r, A, 含义如上.

Output Format

如果完全没有矛盾,输出0,否则输出最先造成矛盾的问题编号

Sample Input

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

Sample Output

3

Limits

10%的数据 \(N \leq 20,Q \leq 20\)

40%的数据 \(N \leq 100,Q \leq 100\)

100%的数据 \(N \leq 10^6,Q \leq 25000, A \leq 10^9\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!