🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Vườn cam sành của thầy Sơn ở Tam Bình (Vĩnh Long) được trồng thẳng hàng thành một lưới gồm ~M~ hàng và ~N~ cột; cây ở hàng ~r~, cột ~c~ gọi là cây ~(r, c)~ ~(1 \le r \le M,~ ~1 \le c \le N)~.

Mùa nắng, thầy Sơn kéo máy bơm tưới vườn ~P~ lần. Lần tưới thứ ~i~ phủ nước lên mọi cây trong một khu hình chữ nhật, được thầy ghi lại bằng hai góc đối diện ~(r_1, c_1)~ và ~(r_2, c_2)~ của khu đó. Vì thầy ghi vội nên hai góc có thể là góc trên-trái và dưới-phải, cũng có thể là góc dưới-phải và trên-trái, hay góc trên-phải và dưới-trái... (không đảm bảo ~r_1 \le r_2~ hay ~c_1 \le c_2~). Hai khu tưới có thể chồng lên nhau; mỗi lần tưới thì mỗi cây trong khu nhận thêm ~1~ lượt nước.

Một cây được gọi là đủ nước nếu sau cả ~P~ lần tưới nó nhận được ít nhất ~K~ lượt nước.

Để chuẩn bị bán cam, thầy Sơn hỏi ~Q~ câu: trong khu hình chữ nhật có hai góc đối diện ~(x_1, y_1)~ và ~(x_2, y_2)~ (cũng không đảm bảo thứ tự), có bao nhiêu cây đủ nước?

Hãy giúp thầy Sơn trả lời tất cả các câu hỏi.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~M, N, K~ ~(1 \le M, N;~ ~M \times N \le 10^6;~ ~0 \le K \le 10^5)~.
• Dòng thứ hai chứa số nguyên ~P~ ~(1 \le P \le 10^5)~.
• ~P~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~r_1, c_1, r_2, c_2~ ~(1 \le r_1, r_2 \le M;~ ~1 \le c_1, c_2 \le N)~ mô tả một lần tưới.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1, y_1, x_2, y_2~ ~(1 \le x_1, x_2 \le M;~ ~1 \le y_1, y_2 \le N)~ mô tả một câu hỏi.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là số cây đủ nước trong khu của câu hỏi thứ ~j~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~M, N \le 100~ và ~P, Q \le 100~.
• Subtask 2 (~30\%~ số điểm): ~Q \le 10~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

Lưu ý: chỉ có ~M \times N \le 10^6~, nên vườn có thể rất "dài" như ~M = 1, N = 10^6~ hoặc ~M = 10^6, N = 1~.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 4 giây.

Sample Input 1

3 4 2
3
1 1 2 3
3 4 2 2
2 1 2 1
2
1 1 3 4
3 3 1 2

Sample Output 1

3
2

Giải thích

Số lượt nước của từng cây sau ba lần tưới:

1 1 1 0
2 2 2 1
0 1 1 1

Các cây đủ nước (ít nhất ~2~ lượt) là ~(2, 1), (2, 2), (2, 3)~. Câu hỏi 1 hỏi cả vườn nên đáp án là ~3~. Câu hỏi 2 hỏi khu hàng ~1..3~, cột ~2..3~, chứa hai cây đủ nước ~(2, 2), (2, 3)~.

Sample Input 2

2 3 0
1
1 1 1 1
1
2 3 1 2

Sample Output 2

4

Giải thích

Với ~K = 0~, mọi cây đều đủ nước (kể cả cây chưa được tưới lần nào), nên khu hàng ~1..2~, cột ~2..3~ có ~4~ cây đủ nước.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).