# D

# 题目大意

给定 NN 个方块的坐标,对于一个时刻,所有方块,会自动下落一格,若最底部一行填满,则清除底部一行
你需要做的是,对于 QQ 个询问(指定方块编号和时刻),判断这个方块是否还存在

# 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int N = 1e6 + 10;
int n, w, q;
int dt[N];
vector<array<int, 2>> col[N]; // 定义二维数组 col,记录每列的方块(包括方块的 x 坐标和编号)
// col[i][j][0] 代表第 i 列的,从下往上数第 j - 1 个方块的行数
// col[i][j][0] 代表第 i 列的,从下往上数第 j - 1 个方块的编号

void solve(){
cin >> n >> w; // 方块数量 列数
for (int i = 1, x, y; i <= n; i++) {
cin >> y >> x;
col[y].push_back({x, i});
}

for (int i = 1; i <= w; i++)
sort(col[i].begin(), col[i].end());

for (int t = 1; t <= 1e9; t++) {
int mx = 0;

for (int i = 1; i <= w; i++) {
if (col[i].size() < t) {
mx = -1;
break;
}

mx = max(mx, col[i][t - 1][0]);
}

if (mx == -1)
break;

for (int i = 1; i <= w; i++)
if (col[i].size() >= t)
dt[col[i][t - 1][1]] = mx;
}


cin >> q;

while (q--) {
int t, p;
cin >> t >> p;

if (!dt[p] || t < dt[p])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝