← 返回题目列表

Codeforces · 1044/A

A. 塔要回家了

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

在宽度为$$$10^9$$$、高度为$$$10^9$$$的棋盘上,行从下到上编号为$$$1$$$到$$$10^9$$$,列从左到右编号为$$$1$$$到$$$10^9$$$。因此,对于棋盘的每个单元格,您可以指定坐标 $$$(x,y)$$$,其中 $$$x$$$ 是列号,$$$y$$$ 是行号。

这个棋盘上每天都有黑白棋子之间的战斗。今天,黑人赢了,但代价是什么?只有车幸存下来,它被赶到了左下角——坐标为$$$(1,1)$$$的单元格。但它仍然很高兴,因为胜利已经赢得了,是时候庆祝了!为此,车需要回家,即在场地的上侧(即编号为 $$$10^9$$$ 的行中的任何单元格中)。

一切都会好起来的,但在比赛结束前,奸诈的白色人物在场上的一些地方施了咒语。咒语有两种类型:

- 垂直。其中每一个都由一个数字 $$$x$$$ 定义。这些咒语会在 $$$x$$$ 和 $$$x+1$$$ 列之间创建一条无限的阻挡线。
- 水平。其中每一个都由三个数字 $$$x_1$$$、$$$x_2$$$、$$$y$$$ 定义。此类咒语会创建一个穿过单元格顶部的阻挡段,这些单元格位于 $$$y$$$ 行以及从 $$$x_1$$$ 到 $$$x_2$$$ 的列中。这些法术的特殊之处在于,某一对这样的法术不可能有共同点。请注意,水平咒语可以与垂直咒语有共同点。

棋盘的示例。

让我们回想一下,车是一颗棋子,一步就能移动到与其初始位置在同一行或同一列的任何点。在我们的任务中,只有在 $$$r_1 = r_0$$$ 或 $$$c_1 = c_0$$$ 且这些单元之间没有阻挡线或阻挡段的情况下,车才能从单元格 $$$(r_0,c_0)$$$ 移动到单元格 $$$(r_1,c_1)$$$ 中(为了更好地理解,请查看示例)。

幸运的是,车可以移除法术,但为此它必须付出巨大的努力,因此,它希望以尽可能少的方式移除法术,之后就可以回家了。找到这个号码!

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$0 \le n,m \le 10^5$$$) — 垂直和水平拼写的数量。

以下 $$$n$$$ 行中的每一行都包含一个整数 $$$x$$$ ($$$1 \le x < 10^9$$$) — 垂直拼写的描述。它将在 $$$x$$$ 和 $$$x+1$$$ 列之间创建一条阻塞线。

以下 $$$m$$$ 行中的每一行都包含三个整数 $$$x_1$$$、$$$x_2$$$ 和 $$$y$$$ ($$$1 \le x_{1} \le x_{2} \le 10^9$$$, $$$1 \le y < 10^9$$$) - 描述水平拼写的数字。它将创建一个阻塞段,该段穿过编号为 $$$y$$$ 的行中从 $$$x_1$$$ 到 $$$x_2$$$ 的列中的单元格的顶部。

保证所有法术都是不同的,并且对于每对水平法术,描述它们的片段确实没有共同点。

输出

在一行中打印一个整数 - 车需要移除的最少咒语数量,以便它可以从单元格 $$$(1,1)$$$ 到达行中编号为 $$$10^9$$$ 的至少一个单元格

示例

输入 #1

2 3
6
8
1 5 6
1 9 4
2 4 2

输出 #1

1

输入 #2

1 3
4
1 5 3
1 9 4
4 6 6

输出 #2

1

输入 #3

0 2
1 1000000000 4
1 1000000000 2

输出 #3

2

输入#4

0 0

输出#4

0

输入 #5

2 3
4
6
1 4 3
1 5 2
1 6 5

输出 #5

2

注意

在第一个示例中,为了让车回家,移除第二个水平咒语就足够了。

第一个示例的插图。左边显示了场地一开始的样子。右侧显示了删除第二个水平拼写后该字段的外观。它还显示了车回家的路径。

在第二个示例中,为了让车回家,移除唯一的垂直咒语就足够了。如果我们试图仅移除一个水平咒语,它将不允许车回家,因为它会被剩余的水平咒语之一(第一个或第二个)从上方阻挡,而在右侧它将被垂直咒语阻挡。

第二个示例的插图。左边显示了场地一开始的样子。右侧显示了删除垂直拼写后的外观。它还显示了车回家的路径。

在第三个示例中,我们有两个穿过整个字段的水平咒语。这些咒语无法被绕过,所以我们需要将它们都移除。

第三个示例的插图。左边显示了场地一开始的样子。右侧显示了删除水平拼写后场地的外观。它还显示了车回家的路径。

在第四个示例中,我们没有咒语,这意味着我们不需要删除任何内容。

在第五个示例中,我们可以删除第一个垂直和第三个水平拼写。

第五个示例的插图。左边显示了场地一开始的样子。右侧显示了删除后的样子。它还显示了车回家的路径。