Diện Tích Phủ Sóng

Buổi 67-68 — Mock IOI
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Có $N$ trạm phát sóng đặt trong khu vực hình chữ nhật. Mỗi trạm thứ $i$ phủ sóng một hình chữ nhật có các cạnh song song với hai trục tọa độ, góc dưới trái tại $(x_{1,i}, y_{1,i})$ và góc trên phải tại $(x_{2,i}, y_{2,i})$.

Hãy tính tổng diện tích phần mặt phẳng được phủ sóng bởi ít nhất một trạm phát sóng.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 50\,000$).
  • $N$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($0 \le x_{1,i} < x_{2,i} \le 10^9$, $0 \le y_{1,i} < y_{2,i} \le 10^9$).

Kết quả

  • In ra một số nguyên duy nhất là diện tích hợp của $N$ hình chữ nhật.

Subtasks

  • Subtask 1 (20%): $N \le 100$, các tọa độ $\le 1000$.
  • Subtask 2 (30%): $N \le 2000$.
  • Subtask 3 (50%): Không có ràng buộc bổ sung.

Ví dụ

Input Output
3
0 0 4 4
2 2 6 6
1 1 3 5
29
Draft saved