Bedao OI Contest 5 - Lại là diện tích hình chữ nhật
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
5.0s
Giới hạn bộ nhớ:
1G
Input:
rect.inp
Output:
rect.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Có ~N~ hình chữ nhật trên mặt phẳng tọa độ. Các hình chữ nhật có thể giao hoặc không giao nhau và có thể trùng nhau.
Cho ~2~ số nguyên ~L~ và ~R~. Đếm số lượng điểm bị phủ bởi ít nhất ~L~ hình chữ nhật, và nhiều nhất ~R~ hình chữ nhật.
Input
Dữ liệu vào từ file văn bản rect.inp:
Dòng đầu tiên gồm ~3~ số nguyên dương ~N~, ~L~, ~R~ (~1 \le L \le R \le N \le 2 \cdot 10^5~).
~N~ dòng tiếp theo gồm ~4~ số nguyên ~x_1~, ~y_1~, ~x_2~, ~y_2~ tương ứng là tọa độ góc trái dưới và góc phải trên của hình chữ nhật thứ ~i~. (~0 \le x_1 \le x_2 \le 10^5, 0 \le y_1 \le y_2 \le 10^5~).
Output
In ra file văn bản rect.out một số nguyên duy nhất là kết quả bài toán.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | 8 | ~N \le 200, 0 \le x_1 \le x_2 \le 200, 0 \le y_1 \le y_2 \le 200~ |
| 2 | 12 | ~0 \le x_1 \le x_2 \le 2 \cdot 10^3, 0 \le y_1 \le y_2 \le 2 \cdot 10^3~ |
| 3 | 10 | ~L = 1, R = N~ |
| 4 | 20 | ~L = R = N~ |
| 5 | 15 | ~L = R~ |
| 6 | 15 | ~N \le 10^4~ |
| 7 | 20 | Không có ràng buộc gì thêm |
Sample Input 1
4 1 1
2 2 6 5
3 3 7 6
7 5 9 7
8 3 10 6
Sample Output 1
25
Sample Input 2
4 1 2
2 2 6 5
3 3 7 6
7 5 9 7
8 3 10 6
Sample Output 2
43
Bình luận
.