#218. 习题 20-3 犁田机器人

习题 20-3 犁田机器人

时间限制:1 sec1 \ sec ;空间限制:128 MB128\ MB

题目描述

猪爷爷为了让自己从无穷无尽的犁田工作中解放出来,于是买了个新机器人替代人手,完成犁田工作。这个机器人可以完成犁田的任务,但是有一个小小的缺点:机器人单次只能犁一个边长是整数的长方形区域。 田地可以看作是一个MMNN列的矩阵,左下角为(1,1)(1,1)。因为田地内可能有树或石头等障碍物,所以需要设定机器人去犁很多不同的长方形(这些长方形允许重叠)。 机器人执行的每个指令包含44个整数:Xll,Yll,Xur,YurXll,Yll,Xur,Yur,分别是要犁的长方形的左下角坐标和右上角坐标。机器人会犁所有的横坐标在 XllXurXll……Xur 并且纵坐标 YllYurYll……Yur 范围内的地。

猪爷爷给机器人下 PP 个指令,每个指令包含一个要犁的长方形区域。 请问:最后到底有多少个方格的地被犁过了?

输入格式

第一行三个整数 N,M,PN,M,P

第二行到第 P+1P+1 行,第 i+1i+1 行四个整数 Xll,Yll,Xur,YurXll,Yll,Xur,Yur,表示第 ii 个指令。

输出格式

一个整数,输出被犁过的方格数。

样例输入

6 4 2
1 1 2 4
1 3 5 4

样例输出

14

样例分析

66 方格宽 44 方格高的田地。 猪爷爷进行了 22 个操作(如下),田地就被成第一次操作被犁的田标记为"*",第二次犁的田标记为"#":

......                  ....              #####.
......                  ....              #####.
......                  ....              ....
......                  ....              ....
                      (1,1)(2,4)          (1,3)(5,4)

则一共 1414 个方格的地被犁过了。

数据范围

对于 100%100\% 的数据: 1X1000,1Y1000,1I1000,1 \le X \le 1000,1 \le Y \le 1000,1 \le I \le1000, $1 \le Xll \le Xur, Xll \le Xur \le X, 1 \le Yll \le Yur,Yll \le Yur \le Y$ 。