琵琶湖
测试数据来自 system/1944
描述
滋贺县的琵琶湖享有盛名,尤其是湖中央的琵琶岛。
琵琶岛不仅外观上是矩形的,而且还被分割为了 n x m 的格子图。每一块格子区域都有着确定的高度。不幸的是,琵琶湖的水位最近开始上涨了,第 i 年湖面的高度将上涨至 i 米。另外一方面,琵琶岛是由松软的土质形成的,且琵琶湖的湖水可以自由渗入到其中。也就是说,如果有一块格子区域的高度不超过当前的水位,则将被淹没。相连的未被淹没的格子(有着公共边的格子区域)将组成一块未被淹没的区域。
现在,小可可希望知道对于指定的某一年来说,琵琶岛被分割为了多少块未被淹没的区域。
格式
输入格式
输入的第一行有两个整数 n 和 m,由一个空格隔开,表示琵琶岛的大小。
之后 n 行,每行有 m 个正整数,在 [1,10^9] 范围内,表示了对应格子区域的高度。
之后一行有一个整数 T。再之后的一行,有 T 个整数 t_j,满足 0<=t_1<=t_2<=...<=t_{T-1}<=t_T<=10^9。
输出格式
在输出中,你的程序应该输出单独一行,包含 T 个整数 r_j 以空格隔开。其中 r_j 表示了在第 t_j 年,未被淹没的区域的个数。
样例1
样例输入1
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5
样例输出1
2 3 1 0 0
限制
对于20%的数据,1<=n<=100, 1<=m<=100, 1<=T<=2000。
有20%的数据,n = 1, 1<=m<=1000, 1<=T<=10^5。
还有20%的数据,n = 2, 1<=m<=1000, 1<=T<=10^5。
对于100%的数据,1<=n<=1000, 1<=m<=1000, 1<=T<=10^5。
来源
AHOI 2015
信息
- ID
- 1876
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者