← 返回题目列表

Codeforces · 1920/A

A. 满足约束

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

Alex 正在解决问题。他对整数 $$$k$$$ 的大小有 $$$n$$$ 限制。约束分为三种类型:

1. $$$k$$$ 必须大于或等于某个整数 $$$x$$$;
2. $$$k$$$ 必须小于或等于某个整数 $$$x$$$;
3. $$$k$$$ 必须不等于某个整数 $$$x$$$。

帮助 Alex 找到满足所有 $$$n$$$ 约束的整数 $$$k$$$ 的数量。保证答案是有限的(存在至少一个 $$$1$$$ 类型的约束和至少一个 $$$2$$$ 类型的约束)。此外,还保证没有两个约束是完全相同的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 约束的数量。

以下 $$$n$$$ 行描述了约束。每行包含两个整数 $$$a$$$ 和 $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$)。 $$$a$$$ 表示约束的类型。如果$$$a=1$$$,$$$k$$$ 必须大于或等于$$$x$$$。如果$$$a=2$$$,$$$k$$$ 必须小于或等于$$$x$$$。如果$$$a=3$$$,$$$k$$$ 必须不等于$$$x$$$。

保证有有限数量的整数满足所有 $$$n$$$ 约束(存在至少一个 $$$1$$$ 类型的约束和至少一个 $$$2$$$ 类型的约束)。还保证没有两个约束是完全相同的(换句话说,所有对 $$$(a, x)$$$ 都是不同的)。

输出

对于每个测试用例,输出一个整数 - 满足所有 $$$n$$$ 约束的整数 $$$k$$$ 的数量。

示例

输入 #1

6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001

输出 #1

7
0
90
0
0
800000000

注意

在第一个测试用例中,$$$k \geq 3$$$ 和 $$$k \leq 10$$$。此外,$$$k \neq 1$$$ 和 $$$k \neq 5$$$。满足约束的可能整数$$$k$$$是$$$3,4,6,7,8,9,10$$$。所以答案是$$$7$$$。

在第二个测试用例中,$$$k \ge 5$$$ 和 $$$k \le 4$$$,这是不可能的。所以答案是$$$0$$$。