Máy quét lưới cổ đại
Đề bài
Mô tả
Để mở khóa căn phòng trung tâm của một phế tích ngoài hành tinh, đoàn thám hiểm phải giải mã một phiến đá cổ được mô hình hóa thành một ma trận hai chiều gồm hàng và cột chứa các số nguyên dương. Các hàng được đánh số từ đến (từ trên xuống dưới) và các cột được đánh số từ đến (từ trái sang phải).
Một mapat là một hình vuông có các cạnh song song với các trục, được xác định bởi ô ở góc dưới bên phải (gọi là ô tiêu điểm) và một số nguyên là độ dài cạnh (). Mapat này phủ tất cả các ô thỏa mãn và .
Giá trị năng lượng của một mapat được tính bằng , trong đó là tổng tất cả các phần tử trong hình vuông và là giá trị của ô tiêu điểm .
Với một hàng cố định và một độ dài cạnh cố định (), gọi là giá trị năng lượng của mapat có ô tiêu điểm , với . Một dãy mapat liên tiếp dọc theo hàng được xác định bởi hai biên với , và tổng gộp của nó là .
Bạn cần xử lý truy vấn loại 1 và truy vấn loại 2:
- Loại 1 : tìm độ dài lớn nhất của một dãy mapat liên tiếp có cạnh trên hàng có tổng gộp . Nếu không có dãy nào như vậy, đáp án là .
- Loại 2 : đếm số cặp với sao cho tổng gộp nằm trong đoạn .
Dữ liệu vào
- Dòng đầu tiên chứa bốn số nguyên , , , (; ).
- dòng tiếp theo, mỗi dòng chứa số nguyên mô tả ma trận (các phần tử là số nguyên dương ).
- dòng tiếp theo, mỗi dòng chứa số nguyên , , mô tả một truy vấn loại 1 ().
- dòng tiếp theo, mỗi dòng chứa số nguyên , , , mô tả một truy vấn loại 2 ().
Trong mọi truy vấn, và .
Dữ liệu ra
Đầu tiên in ra dòng: đáp án của từng truy vấn loại 1 theo thứ tự đã cho. Sau đó in ra dòng: đáp án của từng truy vấn loại 2 theo thứ tự đã cho.
Ràng buộc
- .
- .
- Các phần tử của ma trận là số nguyên dương .
- , .
- Loại 1: .
- Loại 2: .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 2 0 1 3 5 2 4 3 1 2 7 8 1 1 2 2 3 1 2 4 20 1 4 16 |
1 3 |
Truy vấn 1: , hàng : , , ; chỉ dãy có tổng . Truy vấn 2: , hàng : ; dãy có tổng , còn có tổng . |
| 3 3 2 2 2 1 3 1 2 1 3 1 2 2 3 5 1 2 3 1 3 4 9 2 2 7 12 |
0 1 3 2 |
Ví dụ bổ sung (không có trong đề gốc). Loại 1, , hàng : , , đều lớn hơn nên đáp án . Loại 1, , hàng : , đáp án . Loại 2, , hàng : , các tổng gộp là , có tổng () thuộc . Loại 2, , hàng : , , các tổng , có tổng thuộc . |
Bình luận