#P5430. [2018年福建省队集训]俄罗期方块

    ID: 4434 传统题 2000ms 512MiB 尝试: 10 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-数据结构有序集合位运算位集求交按位贪心ST 表位切片并行加法CF2800

[2018年福建省队集训]俄罗期方块

俄罗斯方块

题目描述

游戏在一个足够高、宽为 mm 列的网格上进行。行从下到上依次编号为 1,2,3,…1,2,3,\ldots,列从左到右依次编号为 1,2,…,m1,2,\ldots,m。初始时网格为空。

有 kk 种板块,每种由若干个四连通的单位方块组成。游戏依次生成 nn 个板块,每个板块的形状是给定的某一种。玩家设置其水平位置后,整个板块以固定形状从足够高处竖直下落。

当板块中任一方块的下边界碰到网格底边,或碰到一个已停止的方块的上边界时,整个板块停止下落并固定。上一个板块停止后,才会生成下一个。方块一直保留,满行也不消除。

局面高度是被占据的行的最大编号。求每个板块停止下落后,局面的高度。

输入格式

第一行两个正整数 k,mk,m,分别表示板块种数和网格宽度。

接下来依次描述 kk 种板块。对于第 ii 种板块,先输入两个正整数 hi,wih_i,w_i,其中 1≤wi≤m1\le w_i\le m,再从上到下输入 hih_i 行、每行一个长为 wiw_i 的 01 字符串。矩阵中的 1 表示有方块,0 表示没有方块,所有 1 恰好构成一个四连通块。

下一行一个正整数 nn,表示下落的板块数。

接下来 nn 行,每行两个整数 ti,xit_i,x_i。第 ii 次下落使用第 tit_i 种板块,描述它的整个 01 矩阵左边界到网格左边界的距离为 xix_i 格。保证 1≤ti≤k1\le t_i\le k,0≤xi≤m−wti0\le x_i\le m-w_{t_i}。

输出格式

输出 nn 行,每行一个正整数。第 ii 行表示第 ii 个板块停止后局面的高度。

样例

4 10
3 3
100
111
000
2 4
0000
1111
3 4
0100
0110
0010
2 2
11
11
8
1 3
2 0
3 4
1 7
4 7
3 2
3 4
1 2
2
3
3
3
4
5
5
7

下图是样例 1 中所有板块停止后的局面。图上数字表示该板块是第几个下落的。

样例 1 中 8 个板块停止后的局面

1 1000000000
2 7
1111111
1111111
6
1 999999993
1 999999987
1 999999980
1 999999992
1 999999986
1 999999993
2
4
4
6
8
8

数据范围

对于所有数据,1≤k≤n≤1051\le k\le n\le10^5,1≤m≤1091\le m\le10^9,∑i=1khiwi≤105\sum_{i=1}^k h_iw_i\le10^5。

原赛共有 7 个子任务,每个子任务只有全部数据通过才得分。

子任务 分值 nn mm 板块限制 特殊性质
1 9 ≤100\le100 hi,wi≤10h_i,w_i\le10 无
2 12 ≤1000\le1000 ≤5×104\le5\times10^4 ∑hiwi≤104\sum h_iw_i\le10^4
3 18 ≤5×104\le5\times10^4 hi=1h_i=1,wi≤5×104w_i\le5\times10^4 1、2
4 7 ≤105\le10^5 ≤109\le10^9 ∑hiwi≤105\sum h_iw_i\le10^5 1
5 21 hi=2h_i=2,wi≤5×104w_i\le5\times10^4 2
6 19 ≤5×104\le5\times10^4 ∑hiwi≤5×104\sum h_iw_i\le5\times10^4 无
7 14 ≤105\le10^5 ≤109\le10^9 ∑hiwi≤105\sum h_iw_i\le10^5
  • 特殊性质 1:每种板块的 01 矩阵只含 1。
  • 特殊性质 2:k=1k=1。