#P10732. [2020年省队模拟]网格图

    ID: 9850 传统题 3000ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-扫描线普通线段树栈懒删除

[2020年省队模拟]网格图

题目描述

有一个 nn 行 mm 列的网格,初始时每个格子都是白色。接下来依次执行 BB 次操作,每次把指定格子染黑。指定格子可能已经是黑色。

每次操作之后,反复执行以下规则,直到无法继续染色。若一个白色格子上下左右相邻的格子中至少有两个是黑色,就把这个格子染黑。网格外的位置不计入相邻格子。

求所有操作结束后,网格中黑色格子的总数。

输入格式

第一行三个正整数 n,m,Bn,m,B,分别表示网格的行数、列数和操作次数。

接下来 BB 行,每行两个整数 x,yx,y,表示将第 xx 行第 yy 列的格子染黑。坐标可能重复。

输出格式

一行一个整数,表示最终黑色格子的总数。

样例

3 5 4
1 1
3 1
1 4
2 5
7
6 6 6
1 3
3 1
4 6
6 4
5 5
2 2
36

数据范围

1≤n,m,B≤5×1051\le n,m,B\le5\times10^5,1≤x≤n1\le x\le n,1≤y≤m1\le y\le m。

原赛子任务 特殊限制 原赛分值
1 n≤2n\le2 10
2 n,m≤1000n,m\le1000 20
3 B≤1000B\le1000
4 n,m,B≤5×104n,m,B\le5\times10^4
5 无特殊限制 30

原 PDF 题面