#4473. 扩展版 - 地毯统计

扩展版 - 地毯统计

题目描述:

在一个 n×nn \times n 的方格地面上,铺设了 mm 张矩形地毯。 每张地毯由其左上角坐标 (x1,y1)(x_1, y_1) 和右下角坐标 (x2,y2)(x_2, y_2) 表示。

现在请你计算:有多少个格子被 至少 KK 张地毯覆盖


输入格式:

第一行包含三个正整数 n,m,Kn, m, K,分别表示:

  • 地面为 n×nn \times n 大小;
  • mm 张地毯;
  • 我们要求被覆盖次数不少于 KK 的格子数量。

接下来 mm 行,每行四个正整数:

表示一张地毯的左上角坐标为 (x1,y1)(x_1, y_1),右下角坐标为 (x2,y2)(x_2, y_2)

保证 1x1x2n1 \le x_1 \le x_2 \le n1y1y2n1 \le y_1 \le y_2 \le n


输出格式:

输出一个整数,表示被至少 KK 张地毯覆盖的格子个数。


输入输出样例:

输入 #1

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

输出 #1

7

样例解释:

三张地毯分别覆盖区域如下(数字为被覆盖次数):

01110
01100
01211
00111
00111

被覆盖次数 ≥ 2 的格子共有 7 个。


数据范围:

  • 1n,m10001 \le n,m \le 1000
  • 1Km1 \le K \le m