TopCoder

Thumb head photo2
bb
師宇好可愛 - https://brian.su

User's AC Ratio

94.7% (89/94)

Submission's AC Ratio

28.9% (209/724)

Description

給你很多平面上的矩形,請求出它們覆蓋的總表面積。

Input Format

輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=100,000),代表有n個矩形。
接下來有n列,每列有四個整數 L,R,D,U(0<=L<R<=1,000,000;0<=D<U<=1,000,000)代表矩形的左、右、下、上四個邊界座標。

Output Format

請輸出覆蓋的總面積。

Sample Input

2
1 10 1 10
0 2 0 2

Sample Output

84

Hints

Problem Source

原TIOJ1224 / TIOJ 2008例行賽03-Elite (prob F)。經典問題練習。Problem Setter:Tmt, kelvin。

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 15
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1900 65536 262144
1 1900 65536 262144
2 1900 65536 262144
3 1900 65536 262144
4 1900 65536 262144
5 1900 65536 262144
6 1900 65536 262144
7 1900 65536 262144
8 1900 65536 262144
9 1900 65536 262144
10 1900 65536 262144
11 1900 65536 262144
12 1900 65536 262144
13 1900 65536 262144
14 1900 65536 262144
15 1900 65536 262144
16 1900 65536 262144
17 1900 65536 262144