← 返回题目列表

Codeforces · 1401/E

E. 除平方

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

坐标平面上有一个大小为 $$$10^6 \times 10^6$$$ 的正方形,以四个点 $$$(0, 0)$$$、$$$(0, 10^6)$$$、$$$(10^6, 0)$$$ 和 $$$(10^6, 10^6)$$$ 为顶点。

您将在平面上绘制线段。所有线段都是水平或垂直的,并且至少与正方形的一侧相交。

现在你想知道在绘制完所有线段后这个正方形分为多少块。编写一个程序计算正方形的块数。

输入

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

接下来的 $$$n$$$ 行包含水平段的描述。第 $$$i$$$ 行包含三个整数 $$$y_i$$$、$$$lx_i$$$ 和 $$$rx_i$$$ ($$$0 < y_i < 10^6$$$; $$$0 \le lx_i < rx_i \le 10^6$$$),这意味着该段连接 $$$(lx_i, y_i)$$$ 和$$$(rx_i,y_i)$$$。

接下来的 $$$m$$$ 行包含垂直段的描述。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$ly_i$$$ 和 $$$ry_i$$$ ($$$0 < x_i < 10^6$$$; $$$0 \le ly_i < ry_i \le 10^6$$$),这意味着该线段连接 $$$(x_i, ly_i)$$$ 和$$$(x_i,ry_i)$$$。

保证没有两条线段在同一条线上,并且每条线段至少与正方形的一条边相交。

输出

绘制完所有线段后,打印正方形被分成的块数。

示例

输入 #1

3 3
2 3 1000000
4 0 4
3 0 1000000
4 0 1
2 0 5
3 1 1000000

输出 #1

7

注意

样本是这样的: