Union of Rectangles (large)

2 secs 1024 MB
Tonegawac

問題文


軸または 軸に平行な辺からなる長方形が 個あります。これらを全て重ね合わせてできる図形の面積を求めてください。

制約


verify用なため実行時間制限が厳しいかもしれません。すみません。

入力


入力はすべて整数である。
はそれぞれ 番目の長方形の左上と右下の点の座標である。

N
lx_1 ly_1 rx_1 ry_1
lx_2 ly_2 rx_2 ry_2
.
.
.
lx_n ly_n rx_n ry_n

出力


S

答えを1行に出力してください。 答えは標準的な符号付き64bit整数に収まります。

サンプル


入力1
1
-1000000000 -1000000000 1000000000 1000000000
出力1
4000000000000000000

答えの最大値です。

入力2
4
0 0 10 10
5 5 20 20
7 9 10 25
100 100 200 200
出力2
10315
入力3
2
0 1 20 15
7 3 10 16
出力3
283

Submit


Go (1.14)