TopCoder

User's AC Ratio

91.2% (62/68)

Submission's AC Ratio

29.8% (131/439)

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 65536
1 1900 65536 65536
2 1900 65536 65536
3 1900 65536 65536
4 1900 65536 65536
5 1900 65536 65536
6 1900 65536 65536
7 1900 65536 65536
8 1900 65536 65536
9 1900 65536 65536
10 1900 65536 65536
11 1900 65536 65536
12 1900 65536 65536
13 1900 65536 65536
14 1900 65536 65536
15 1900 65536 65536
16 1900 65536 65536
17 1900 65536 65536