#P11756. [COTS 2014] 土地划分 / KRAVE
[COTS 2014] 土地划分 / KRAVE
题目描述
Mirko 有一块草地,宽 米,高 米,边和坐标轴平行,草地的左下角位于 处,右上边缘位于 处。
Mirko 决定在他的草地上建造水平和垂直围栏。按如下方式执行此作:首先,选择一个点 ,到目前为止没有栅栏通过该点,并决定新栅栏是水平的还是垂直的。之后,他沿所选方向建造一个栅栏,直到他遇到另一个栅栏并将它们连接在那里,然后再进行下一次操作。
这是关于样例 建造过程的解释。
通过栅栏的划分后,田地会被划分成若干个矩形,对于每个矩形而言,矩形边缘有栅栏,里面没有栅栏。具体的,每次划分会把一个矩形划分为两个新的矩形。
现在有若干对建造栅栏步骤的描述,你要按升序输出新产生的两个矩形的面积。
输入格式
第一行有两个整数 ,表示草地的宽和高。
第二行一个整数 ,表示建造栅栏的步骤数。
接下来 行,每行三个整数 ,表示从 开始,若 建造一个水平栅栏,若 建造竖直栅栏。
保证在那一刻前,没有栅栏经过 。
输出格式
行,每行两个升序整数表示新产生的矩形面积。
9 7
5
3 3 2
7 2 1
6 3 2
5 4 1
1 4 1
21 42
12 30
15 15
6 9
9 12
4 4
3
2 2 2
1 2 1
3 2 1
8 8
4 4
4 4
9 7
10
6 1 2
2 6 2
8 5 2
5 2 2
4 3 1
1 2 1
7 6 1
3 4 1
1 4 1
7 2 1
21 42
14 28
7 14
7 21
9 12
4 10
2 12
3 9
4 6
4 8
提示
-
Subtask ( pts): 。
-
Subtask ( pts):不会出现垂直建造和竖直建造穿插进行的情况。
-
Subtask ( pts):$1\le N \le 10^5,2\le A,B\le10^5,0<X<A,0<Y<B,D \in\{1,2\}$。