C - Checkered Stamps
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
10^9 \times 10^9 のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表すことにします。グリッドのそれぞれのマスは白か黒のどちらかの色になります。最初は全てのマスの色は白です。
今から高橋君は、合計 N 個のスタンプを押します。i 回目 (1 ≤ i ≤ N) は、縦 H_i マス、横 W_i マスの長方形のスタンプを、 左上が (R_i, C_i) と重なるように押します (スタンプの押される部分がグリッドからはみ出すことはありません)。このスタンプは、全体が白いグリッドに押したときに市松模様ができるように設計されており、スタンプの上から p 行目、左から q 列目 (1 ≤ p ≤ H_i, 1 ≤ q ≤ W_i) が押されたマスは、 p+q が偶数ならば白と黒が反転し、奇数ならば変化しません。
N 個のスタンプを押した後、グリッドに黒いマスがいくつあるかを求めてください。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ H_i ≤ 10^9
- 1 ≤ W_i ≤ 10^9
- 1 ≤ R_i ≤ 10^9
- 1 ≤ C_i ≤ 10^9
- H_i + R_i - 1 ≤ 10^9
- W_i + C_i - 1 ≤ 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 W_1 R_1 C_1 : H_N W_N R_N C_N
出力
N 個のスタンプを押した後の黒いマスの個数を出力せよ。
入力例 1
3 3 3 1 1 2 3 2 1 1 2 3 1
出力例 1
7
下の画像はグリッドの左上 3 \times 3 マスの変化を表しています。
入力例 2
5 66518928 212072708 158598694 334005903 54102801 860639145 839206374 16401163 226949335 660240556 476286324 65656871 153262413 54385827 719562883 5920096 496820604 90893558 460217283 428740659
出力例 2
130526013386872287