题目详情题解（0）讨论（0）提交记录（0）

AT_abc449_f.[ABC449F] Grid Clipping

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 HH 行 WW 列的网格。第 rr 行从上往下数，第 cc 列从左往右数，称为单元格 (r,c)(r,c)。每个单元格被涂成黑色或白色：对于 k=1,2,…,Nk=1,2,\ldots,N，单元格 (Rk,Ck)(R_k,C_k) 是黑色，其余 HW−NHW-N 个单元格均为白色。

请你计算，这个网格中有多少个 hh 行 ww 列的矩形区域，使得该区域内所有单元格都是白色。

更严格地说，求满足以下所有条件的整数对 (r0,c0)(r_0,c_0) 的数量：

  • 1≤r0≤H−h+11 \le r_0 \le H-h+1
  • 1≤c0≤W−w+11 \le c_0 \le W-w+1
  • 对于所有满足 0≤i<h, 0≤j<w0 \le i < h,\ 0 \le j < w 的整数对 (i,j)(i,j)，单元格 (r0+i,c0+j)(r_0+i, c_0+j) 都是白色。

输入格式

输入从标准输入读入，格式如下：

HH WW hh ww NN R1R_1 C1C_1 R2R_2 C2C_2 ⋮\vdots RNR_N CNC_N

输出格式

输出答案。

输入输出样例

  • 输入#1

    3 4 2 2 3
1 3
2 4
3 1

    输出#1

    2

  • 输入#2

    4 4 3 2 2
2 2
3 4

    输出#2

    0

  • 输入#3

    449 449 3 14 0

    输出#3

    194892

  • 输入#4

    31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

    输出#4

    12

说明/提示

样例解释 1

下图中红色框出的两个矩形区域都满足要求。

样例解释 2

没有任何矩形区域满足所有条件。

数据范围

  • 1≤h≤H≤1091 \le h \le H \le 10^9
  • 1≤w≤W≤1091 \le w \le W \le 10^9
  • 0≤N≤2×1050 \le N \le 2 \times 10^5
  • 1≤Rk≤H1 \le R_k \le H
  • 1≤Ck≤W1 \le C_k \le W
  • (Rk1,Ck1)≠(Rk2,Ck2) (k1≠k2)(R_{k_1}, C_{k_1}) \neq (R_{k_2}, C_{k_2})\ (k_1 \neq k_2)
  • 所有输入值都是整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页