← 返回题目列表

AtCoder · yahoo_procon2019_final_c

C. 方格邮票

中文机器翻译题面 查看原题

配点 : 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