Quần đảo khi nước dâng

Buổi 25 — Disjoint Set Union Data-structures sorting
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho một vùng biển kích thước $R \times C$, ô $(i, j)$ có độ cao $H_{i,j}$. Có $Q$ truy vấn, mỗi truy vấn cho một mực nước $W$. Khi mực nước là $W$, chỉ những ô có $H_{i,j} > W$ mới nhô lên khỏi mặt nước. Hai ô nhô lên nối với nhau nếu chung cạnh. Hãy đếm số lượng hòn đảo (thành phần liên thông của các ô nhô lên) ứng với mỗi truy vấn.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $R, C, Q$ ($1 \le R \cdot C \le 10^5, 1 \le Q \le 10^5$).
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $H_{i,j}$ ($0 \le H_{i,j} \le 10^9$).
  • Dòng cuối cùng chứa $Q$ số nguyên $W_1, W_2, \dots, W_Q$ ($0 \le W_k \le 10^9$).
Dữ liệu ra
  • In ra $Q$ số nguyên trên một dòng, số thứ $k$ là số hòn đảo khi mực nước là $W_k$.
Ví dụ
Input Output
2 3 3
1 5 2
4 2 6
0 3 5
1 3 1
Giới hạn
  • $1 \le R \cdot C \le 10^5, 1 \le Q \le 10^5$
Draft saved