Quần đảo khi nước dâng
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion