← 返回题目列表

AtCoder · maximum_2013_h

H. 埼玉的矛盾

中文机器翻译题面 查看原题

問題

埼玉(暴躁装甲特工秘密协会) n 由武装人员组成的秘密组织。 SAITAMA的每位成员都有 1, 2, ..., n 已被分配一个唯一的会员编号。 他们夜以继日地训练,以摧毁他们的竞争对手组织 GUNMA(大规模特工的伟大终极国家)。 因此,他们总是很在意自己在组织内的实力排名,每天的对话都是“我比那家伙强”、“我是B班第一,我比50岁以上的人都强”、“他是我们埼玉人中最弱的”之类的话。

SAITAMA 的任意两名成员之间都存在权力关系。 两名成员 a, b ,a 表示 b 更强或a 表示 b 要么更弱,要么更弱。 这些权力关系中的两种,或者更准确地说,“较强”和“较弱”关系,满足传递律和非自反律。 即3名成员 a, b, c ,a 是 b 更强,b 是 c 当更强时,总是 a 表示 c 会更强。 另外,a 是 a 没有人比自己更强。对于“较弱”的关系也是如此。

A先生是群马的间谍,在偷听埼玉成员的谈话时,注意到他们所谈论的权力关系存在矛盾。 不过,由于埼玉是一个由极其庞大的成员组成的组织,因此尚不清楚究竟是哪一种说法引起了矛盾。 甚至认为存在矛盾的看法也可能是一种误解。

幸运的是,A先生记住了SAITAMA成员所说的一切以及他们说的顺序。 奇怪的是,他们只说“不。 p 的成员编号为 l 以上 r 似乎是“比下面的任何人都强/弱”的形式。

A先生不惜一切代价想要找出矛盾的原因,他想找出SAITAMA成员的第一个与之前的声明相矛盾的声明。 换句话说,当话语按时间顺序排列时,从第一个开始 直到 k-1 的语句序列不包含任何矛盾,但是 一个整数,使得直到 k 的语句序列包含矛盾。 我想识别 k 。 你的任务是为A先生找出埼玉成员发表的最先出现矛盾的言论的数量。

入力

输入将以以下格式从标准输入提供。

n m
p_1 c_1 l_1 r_1
p_2 c_2 l_2 r_2
:
p_m c_m l_m r_m
  1. 第一行两个整数 n 和 m 由半角空格分隔。
    • n 是 SAITAMA 的会员数量,1 ≦ n ≦ 1,000,000,000 很满意。
    • m 是 SAITAMA 成员发表的言论数量,1 ≦ m ≦ 1,000 很满意。
  2. 从第二行开始 m+1 至行 m 行按时间顺序提供了SAITAMA成员的发言信息。
    • 这些行 i 行目 (1 ≦ i ≦ m) 是 一个整数,提供有关第 i 条评论的信息 p_i、文字 c_i、整数 l_i 和整数 第 r_i 由半角空格分隔。
    • i 语句中信息的含义如下。 对于
      • c_i 是 s ,“数量 p_i 的成员已编号 l_i 以上 r_i 比任何编号较低的成员都强。
      • c_i 是 w ,“数量 p_i 的成员已编号 l_i 以上 r_i 比下面任何编号的成员都要弱。
    • c_i 表示 s 或 w 。
    • p_i 表示 1 ≦ p_i ≦ n 很满意,l_i 和 r_i 表示 1 ≦ l_i ≦ r_i ≦ n 很满意。

出力

打印一行中第一次出现矛盾的语句的编号。
如果没有矛盾的话, 在一行上输出0 。
输出应为标准输出,并在末尾输出换行符。

入力例 1

4 5
4 w 1 3
3 w 2 2
2 s 3 4
3 s 1 1
1 s 2 2

出力例 1

5
  • 到第四个陈述为止都没有矛盾,但最后一个陈述是矛盾的。
    • 从到第四条语句的信息中,我们可以看到成员2强于成员3,成员3强于成员1,因此根据传递律我们可以说成员2强于成员1。
    • 然而,第五条语句说成员1比成员2强,这是一个矛盾。

入力例 2

2 4
1 w 2 2
1 s 2 2
2 w 1 1
2 s 1 1

出力例 2

2
  • 第二个陈述与第一个陈述相矛盾,因为成员 1 不可能弱于成员 2,成员 1 也不可能强于成员 2。
  • 后续陈述也存在矛盾,但第一个矛盾陈述的编号是 2 就是答案。

入力例 3

1000000000 4
1 w 5 100000
1000000 s 100 888888
1000 w 10000 10000
1000000000 s 1 999999999

出力例 3

0
  • 不存在矛盾。看来数字的大小关系和幂关系是一样的。