Nhà của đàn khỉ
Đề bài
Mô tả
Đàn khỉ vừa chuyển đến một khu rừng hình chữ nhật, có thể mô hình hóa thành một bảng gồm hàng và cột. Các hàng được đánh số từ đến theo hướng từ Bắc xuống Nam, các cột được đánh số từ đến theo hướng từ Tây sang Đông. Ô ở hàng thứ và cột thứ được ký hiệu là . Trên ô này có một cái cây cao .
Đàn khỉ muốn chọn một ô làm nhà. Để di chuyển giữa các cây cho thuận tiện, chúng muốn mọi cây nằm cùng hàng hoặc cùng cột với nhà của chúng đều có chiều cao bằng chiều cao của cây ở nhà.
Nói cách khác, nếu đàn khỉ chọn ô làm nhà thì điều kiện sau phải đúng: với mọi ô , nếu thì .
Cho kích thước khu rừng và chiều cao của mọi cây, hãy đếm số ô mà đàn khỉ có thể chọn làm nhà.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ test. Tiếp theo là bộ test, mỗi bộ test gồm:
- Dòng đầu tiên chứa hai số nguyên và (), kích thước khu rừng.
- Dòng thứ trong dòng tiếp theo chứa số nguyên (), chiều cao của các cây.
Dữ liệu vào đảm bảo tổng các giá trị trong mọi bộ test không vượt quá , và tổng các giá trị trong mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một số nguyên là số ô mà đàn khỉ có thể chọn làm nhà.
Ràng buộc
- ; tổng và tổng trên mọi bộ test đều không vượt quá .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 1 10 2 3 2 5 2 2 2 2 3 3 1 1 1 1 1 1 1 1 1 |
1 2 9 |
Ở bộ test thứ nhất, khu rừng chỉ có một cây; đàn khỉ có thể chọn cây đó vì không có cây nào khác. Ở bộ test thứ hai, đàn khỉ có thể chọn ô hoặc . Ở bộ test thứ ba, mọi cây cao bằng nhau nên ô nào cũng chọn được. |
| 2 2 2 1 2 3 4 3 4 5 5 5 5 1 5 2 5 5 5 5 5 |
0 4 |
Ví dụ này không có trong đề gốc. Ở bộ test thứ hai, các ô chọn được là , , và . |
Bình luận