5. JOI 2022 - Sandcastle 2
JOI đang chơi xây lâu đài cát trên bãi biển. Lâu đài nằm trong một vùng hình chữ nhật trên cát. Vùng này được biểu diễn bằng một lưới có \(H\) hàng và \(W\) cột: các hàng được đánh số từ bắc xuống nam, các cột từ tây sang đông. Ô ở hàng \(i\) (\(1 \le i \le H\)), cột \(j\) (\(1 \le j \le W\)) có độ cao \(A_{i,j}\). Độ cao của tất cả các ô đôi một khác nhau.
Trên lâu đài cát này, JOI thực hiện các hành động sau:
- Chọn một ô bất kỳ làm điểm xuất phát.
- Từ ô hiện tại, di chuyển tới một ô kề cạnh theo một trong bốn hướng đông, tây, nam, bắc có độ cao nhỏ hơn. Lặp lại hành động này không hoặc nhiều lần.
Sau cùng, khi nhìn từ trên xuống, toàn bộ các ô mà JOI đã ghé qua tạo thành đúng một vùng hình chữ nhật.
Cho độ cao của các ô, hãy đếm số vùng hình chữ nhật khác nhau có thể là tập hợp các ô JOI đã ghé qua.
Dữ liệu vào
Dữ liệu được cho từ đầu vào chuẩn theo định dạng:
H W
A_{1,1} A_{1,2} ... A_{1,W}
A_{2,1} A_{2,2} ... A_{2,W}
...
A_{H,1} A_{H,2} ... A_{H,W}
Tất cả các giá trị đầu vào đều là số nguyên.
Dữ liệu ra
In ra một dòng chứa số vùng hình chữ nhật khác nhau có thể là tập hợp các ô mà JOI đã ghé qua.
Ràng buộc
- \(H \ge 1\).
- \(W \ge 1\).
- \(H \times W \le 50\,000\).
- \(1 \le A_{i,j} \le 10\,000\,000\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
- \(A_{i_1,j_1} \ne A_{i_2,j_2}\) với mọi hai ô phân biệt \((i_1,j_1) \ne (i_2,j_2)\).
Phân nhóm
- Nhóm 1 (9 điểm): \(H=1\).
- Nhóm 2 (10 điểm): \(H \times W \le 100\).
- Nhóm 3 (5 điểm): \(H \times W \le 1500\).
- Nhóm 4 (56 điểm): \(H \times W \le 7000\).
- Nhóm 5 (20 điểm): Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
1 5
2 4 7 1 5Output
10Note
Có \(10\) vùng hình chữ nhật có thể là tập hợp các ô JOI đã ghé qua, như hình dưới đây, nên đáp án là \(10\).
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1\), \(2\), \(3\), \(4\), \(5\).
Ví dụ 2
Input
3 2
18 10
19 12
17 13Output
15Note
Có \(15\) vùng hình chữ nhật có thể là tập hợp các ô JOI đã ghé qua, như hình dưới đây, nên đáp án là \(15\).
Ví dụ này thỏa mãn ràng buộc của các nhóm \(2\), \(3\), \(4\), \(5\).
Ví dụ 3
Input
3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90Output
65Note
Chẳng hạn, ba vùng hình chữ nhật dưới đây đều có thể xuất hiện. Tính cả những vùng khác, có tổng cộng \(65\) vùng, nên đáp án là \(65\).
Ví dụ này thỏa mãn ràng buộc của các nhóm \(2\), \(3\), \(4\), \(5\).
Nguồn
JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.