banner

Bài tập: Phần thưởng

Đề bài
Mã bài: Bonus
Kiểu chấm: OI
Dữ liệu nhập: Nhập chuẩn
Kết quả xuất: Xuất chuẩn
Giới hạn thời gian: 1 giây
Được tạo bởi: Trần Đức Doanh
Nội dung:

Hiếu là người thắng cuộc trong một cuộc thi “Tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do trung tâm TAS tài trợ. Các phần thưởng được bố trí trên một bảng kích thước m x n, các dòng của bảng được đánh số từ 1 đến m, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i, j) và trên ô đó chứa một món quà có giá trị là aij (1 ≤ i m, 1 ≤ j n).

Để nhận phần thưởng, Hiếu cần trả lời các câu hỏi có dạng: “Cho một hình chữ nhật con có ô trái trên là ô (x,y) và ô phải dưới là ô (u,v), cần đưa ra tổng giá trị các phần quà trong hình chữ nhật con này”.

Yêu cầu: Cho giá trị các phần quà được đặt trên bảng và q bộ xk, yk , uk, vk (k = 1, 2, ..., q) tương ứng với q truy vấn, hãy đưa ra các câu trả lời cho q truy vấn.

Dữ liệu nhập:

Dòng thứ nhất chứa ba số nguyên dương m, n, q (q ≤ m x n);

Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên dương, số thứ j aij (aij ≤ 106);

Dòng thứ k trong số q dòng tiếp theo chứa 4 số nguyên dương xk, yk , uk, vk (k = 1, 2, ..., q).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả xuất:  

Gồm q dòng, mỗi dòng chứa một số là câu trả lời cho một truy vấn theo thứ tự như trong dữ liệu nhập

Ví dụ:

Nhập

Xuất

4 2 2

2 2

3 0

0 1

4 6

1 1 2 2

1 2 4 2

7

9

 


Xem hướng dẫn cách làm bài
Để làm bài thì bạn cần phải đăng nhập