← 返回题目列表

AtCoder · joi2015ho_e

E. 壁垒

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

配点: 100 点

历史学家JOI教授正在研究曾经存在的IOI王国。

根据以往的研究,IOI王国是 H 行,横 W 它具有矩形形状,分为单元列。 IOI王国的首都被城墙包围以进行防御。

IOI王国首都周围的城墙具有以下形状。城堡墙有一个固定值,称为其尺寸。尺寸 s (s \geqq 3) 的城墙是什么? 从s \times s 除外周以外的正方形区域 (s - 2) \times (s - 2) 删除了方形区域。

据考证,首都周围的城墙尺寸为 L 就是这样。据了解,IOI王国的一些广场上没有城墙。

JOI教授想知道有多少种可能的城墙可供进一步研究。

課題

IOI 给定王国的大小、城墙的最小尺寸以及已知不存在城墙的方格的信息,编写一个程序来找出可能有多少个城墙。


入力

从标准输入读取以下数据。

  • 1 行包含一个整数 H, W, L, P 以空格作为分隔符。这意味着IOI王国是 H 行,横 W 它有一个长方形的形状,分为正方形的柱子,城堡墙的大小是 L 仅此而已,已知城墙不存在的方格是 P 表示存在一个正方形。
  • 继续 P 行 i 行目 (1 \leqq i \leqq P) 是一个整数 A_i, B_i 以空格作为分隔符。这是来自IOI王国之上。 A_i 线,从左起 B_i 表示已知该列中的方格内没有城墙。

出力

表示可能的城堡墙数量的整数被发送到标准输出。 输出为 1 行。


制限

所有输入数据满足以下条件。

  • 1 \leqq H \leqq 4\,000.
  • 1 \leqq W \leqq 4\,000.
  • 3 \leqq L \leqq H 和 满足 3 \leqq L \leqq W.
  • 0 \leqq P \leqq 100\,000.
  • 1 \leqq A_i \leqq H (1 \leqq i \leqq P).
  • 1 \leqq B_i \leqq W (1 \leqq i \leqq P).
  • (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq P).

小課題

小課題 1 [4 点]

满足以下条件。

  • H \leqq 500.
  • W \leqq 500.

小課題 2 [16 点]

  • 0 \leqq P \leqq 10 满意。

小課題 3 [80 点]

没有其他限制。


入力例 1

5 5 3 2
2 2
4 3

出力例 1

4

在此输入示例中,可能的城堡墙如下: 4 以下是可能的。然而,× 指示的方格是已知没有城墙的方格。


入力例 2

7 8 4 3
2 2
3 7
6 5

出力例 2

13

入力例 3

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

出力例 3

7050792912