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

AT_abc370_d.[ABC370D] Cross Explosion

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

有一个网格，网格中有 HH 行和 WW 列。让 (i,j)(i, j) 表示从上往下第 ii 行，从左往上第 jj 列的单元格。
最初，每个单元格中都有一面墙。
按照下面给出的顺序处理 QQ 个查询后，求剩余墙的数量。

在第 qq 次查询中，我们给出了两个整数 RqR_q 和 CqC_q 。
您在 (Rq,Cq)(R_q, C_q) 处放置了一枚炸弹来摧毁墙壁。结果会发生以下过程。

  • 如果在 (Rq,Cq)(R_q, C_q) 处有一堵墙，则摧毁这堵墙并结束进程。
  • 如果 (Rq,Cq)(R_q, C_q) 处没有墙壁，则摧毁从 (Rq,Cq)(R_q, C_q) 向上、向下、向左、向右观察时出现的第一面墙壁。更确切地说，以下四个过程是同时进行的：
    • 如果存在一个 i<Rqi \lt R_q ，使得在 (i,Cq)(i, C_q) 处有一堵墙，而在所有 i<k<Rqi \lt k \lt R_q 的 (k,Cq)(k, C_q) 处都没有墙，则摧毁 (i,Cq)(i, C_q) 处的墙。
    • 如果存在一个 i>Rqi \gt R_q ，使得在 (i,Cq)(i, C_q) 处有一堵墙，而在所有 Rq<k<iR_q \lt k \lt i 的 (k,Cq)(k, C_q) 处都没有墙，则破坏 (i,Cq)(i, C_q) 处的墙。
    • 如果存在一个 j<Cqj \lt C_q ，使得在所有 j<k<Cqj \lt k \lt C_q 中， (Rq,j)(R_q, j) 处有一堵墙，而 (Rq,k)(R_q, k) 处没有墙，则破坏 (Rq,j)(R_q, j) 处的墙。
    • 如果存在一个 j>Cqj \gt C_q ，使得在 (Rq,j)(R_q, j) 处有一堵墙，而在所有 Cq<k<jC_q \lt k \lt j 的 (Rq,k)(R_q, k) 处没有墙，则破坏 (Rq,j)(R_q, j) 处的墙。

输入格式

第一行 33 个整数 H,W,QH,W,Q。

接下来每行 22 个整数 R,CR,C，表示在坐标 R,CR,C 出放置了一枚炸弹。

输出格式

输出一个整数，表示最后剩下多少堵墙。

输入输出样例

  • 输入#1

    2 4 3
1 2
1 2
1 3

    输出#1

    2

  • 输入#2

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

    输出#2

    10

  • 输入#3

    4 3 10
2 2
4 1
1 1
4 2
2 1
3 1
1 3
1 2
4 3
4 2

    输出#3

    2

说明/提示

  • 1≤H,W1 \leq H, W
  • H×W≤4×105H \times W \leq 4 \times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • 1≤Rq≤H1 \leq R_q \leq H
  • 1≤Cq≤W1 \leq C_q \leq W
  • 所有输入值均为整数。

Translate by DeepL,Manually verified.

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

首页