#149. Parity Game

Parity Game

题目描述

有一个长度为 n 的未知 0/1 序列。按顺序给出 m 条断言:区间 [l,r] 中 1 的数量为奇数或偶数。找出最长的前缀,使这些断言能够同时为真。

输入格式

第一行 n,第二行 m;随后 m 行为 l、r 和 odd 或 even。

输出格式

输出最大合法前缀长度。如果第 k 条第一次产生矛盾,应输出 k−1。

样例输入

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

样例输出

3

题意整理;原题与输入输出格式对照。