← 返回题目列表

AtCoder · gigacode_2019_f

F. 衣柜摆放

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

配点: 100 点

問題文

Gigacord 买了房子。这房子在左边和右边 H 分割,之前和之后 W 分割总计 它分为 H \times W 部分。从左边开始 从前面数第 i th,从前面 j 第一个方格 表示为 (i, j) 。

很快 对象放置在 N 部分中。i 该项目是一个分区 (r_i, c_i) 它占据了整个区域。而且,这些物体不会移动。

Gigacord 在这所房子里有一个壁橱。 1 我决定安装一个。壁橱必须是与房屋外墙平行的矩形,壁橱所在区域不得放置任何物品。不过,地震发生时衣柜移动的话就不好了,所以可以考虑以下摆放方式: 1 我决定选择一个。

  • 无论您尝试向哪个方向移动衣柜而不改变其方向,它都会撞到物体或房屋的外墙,并且您将无法移动它。

例如,您可以按如下方式布置衣柜。

但是,不符合条件的衣柜是不能放置的。

找出满足条件的壁橱排列数量。

制約

  • 1 \leq H \leq 5 \ 000
  • 1 \leq W \leq 5 \ 000
  • 0 \leq N \leq 201 \ 900
  • 1 \leq r_i \leq H
  • 1 \leq c_i \leq W
  • N 物品均放置在不同的隔间中
  • 输入都是整数

部分点

这个问题被分成了几个子任务,如果你正确回答了该子任务的所有测试用例,那么你就被认为已经正确回答了“这个子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (2 点) H = 1, W = 1
  2. (11 点) H = 1, W \leq 25
  3. (11 点) H \leq 25, W \leq 25
  4. (19 点) N \leq 10
  5. (16 点) H \leq 100, W \leq 100
  6. (17 点) H \leq 350, W \leq 350
  7. (19 点) H \leq 1500, W \leq 1500
  8. (5 分) 没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

H W
N
r_1 c_1
r_2 c_2
 : :
r_N c_N

出力

请输出即使发生地震也不会移动的衣柜布置数量。

注意

由于输入量较大,建议使用高速输入/输出(例如C++的scanf/printf)。