#P11756. [COTS 2014] 土地划分 / KRAVE

[COTS 2014] 土地划分 / KRAVE

题目描述

Mirko 有一块草地,宽 AA 米,高 BB 米,边和坐标轴平行,草地的左下角位于 (0,0)(0,0) 处,右上边缘位于 (A,B)(A,B) 处。

Mirko 决定在他的草地上建造水平和垂直围栏。按如下方式执行此作:首先,选择一个点 (X,Y)(X,Y),到目前为止没有栅栏通过该点,并决定新栅栏是水平的还是垂直的。之后,他沿所选方向建造一个栅栏,直到他遇到另一个栅栏并将它们连接在那里,然后再进行下一次操作。

这是关于样例 11 建造过程的解释。

通过栅栏的划分后,田地会被划分成若干个矩形,对于每个矩形而言,矩形边缘有栅栏,里面没有栅栏。具体的,每次划分会把一个矩形划分为两个新的矩形。

现在有若干对建造栅栏步骤的描述,你要按升序输出新产生的两个矩形的面积。

输入格式

第一行有两个整数 A,BA,B,表示草地的宽和高。

第二行一个整数 NN,表示建造栅栏的步骤数。

接下来 NN 行,每行三个整数 X,Y,DX,Y,D,表示从 (X,Y)(X,Y) 开始,若 D=1D=1 建造一个水平栅栏,若 D=2D=2 建造竖直栅栏。

保证在那一刻前,没有栅栏经过 (X,Y)(X,Y)

输出格式

NN 行,每行两个升序整数表示新产生的矩形面积。

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 111010 pts): N103N \le 10^3

  • Subtask 223030 pts):不会出现垂直建造和竖直建造穿插进行的情况。

  • Subtask 336060 pts):$1\le N \le 10^5,2\le A,B\le10^5,0<X<A,0<Y<B,D \in\{1,2\}$。