TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

90.8% (258/284)

Submission's AC Ratio

26.0% (607/2335)

Tags

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 1

2
1 10 1 10
0 2 0 2

Sample Output 1

84

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 15

Testdata and Limits

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