問題一覧 > 通常問題

No.1074 増殖

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 69
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : Kiri8128Kiri8128
5 ProblemId : 2577 / 出題時の順位表
問題文最終更新日: 2020-05-16 01:52:50

問題文

何も描かれていないxy座標平面がある。
ここに左下の座標が($Xa$,$Ya$)、右上の座標が($Xb$,$Yb$)の原点を内部に含む四角形を描き、内部は塗りつぶす。
四角形の各辺はx軸もしくはy軸のいずれかに平行である。
四角形は$1$番目の四角形から$N$番目の四角形まで1つずつ増えていく。
四角形が増えるたびに総面積がいくつ増えるか答えよ。

入力

$N$
$Xa_1$ $Ya_1$ $Xb_1$ $Yb_1$
$Xa_2$ $Ya_2$ $Xb_2$ $Yb_2$
$\vdots $
$Xa_N$ $Ya_N$ $Xb_N$ $Yb_N$

$N$は正の整数。$1 \le N \le 40000$。
($Xa_i$,$Ya_i$)は$i$番目の四角形の左下の座標。
$Xa_i$、$Ya_i$は負の整数。$-20000 \le Xa_i,Ya_i \le -1$。
($Xb_i$,$Yb_i$)は$i$番目の四角形の右上の座標。
$Xb_i$、$Yb_i$は正の整数。$1 \le Xb_i,Yb_i \le 20000$。

出力

答えを$N$行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2
-2 -2 1 1
-1 -1 2 2
出力
9
5

最初の四角形の面積は9。
次の四角形の面積は9であるが、最初の四角形との重複部分は除くので増えた部分の面積は5。

サンプル2
入力
3
-1 -2 1 2
-2 -1 2 1
-3 -3 3 3
出力
8
4
24

サンプル3
入力
2
-1 -1 1 1
-1 -1 1 1
出力
4
0

増えないこともありますね。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。