#P17853. [Ontak2019]PAI

[Ontak2019]PAI

— 按图案涂色

有一个无限大的白色像素平面。依次执行 nn 条指令,每条指令把一部分像素涂黑;已经涂黑的像素始终保持黑色。求最后黑色像素的数量。

每条指令给出 x1,y1,x2,y2,px_1,y_1,x_2,y_2,p。其中 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2) 是矩形的两个对角,边界像素也包括在矩形内。pp 是一个 16 位非负整数,用来描述 4×44\times4 图案 PP:P[x][y]P[x][y] 等于 pp 的第 4x+y4x+y 位,最低位编号为 00。

对所有 0≤dx≤x2−x10\le dx\le x_2-x_1、0≤dy≤y2−y10\le dy\le y_2-y_1,如果 P[dx mod 4][dy mod 4]=1P[dx\bmod4][dy\bmod4]=1,就把像素 (x1+dx,y1+dy)(x_1+dx,y_1+dy) 涂黑。注意图案的起点是当前矩形的左下角坐标 (x1,y1)(x_1,y_1),不是全局原点。

输入格式

第一行一个整数 nn。接下来 nn 行,每行五个整数 x1,y1,x2,y2,px_1,y_1,x_2,y_2,p。

输出格式

输出一个整数,表示最终黑色像素数量。

数据范围

1≤n≤400001\le n\le40000,x1≤x2x_1\le x_2,y1≤y2y_1\le y_2,0≤p≤655350\le p\le65535。

原题文字规定各坐标在 [0,109][0,10^9] 内,但原题最后一组样例含有大于 10910^9 的坐标。这里保留原样例并记录这一不一致;标程的坐标运算和答案均使用 64 位整数,支持这些样例值。

子任务 附加限制 分值
1 n≤100n\le100,坐标不超过 100100 9
2 n≤200n\le200 22
3 n≤2000n\le2000 48
4 无 21

样例 1

输入:

1
10 20 30 50 65535

输出:

651

样例 2

输入:

2
10 20 30 50 65535
0 30 40 40 65535

输出:

871

样例 3

输入:

2
10 20 30 50 42405
0 30 40 40 42405

输出:

436

样例 4

输入:

2
10 20 30 50 42405
0 30 40 40 23130

输出:

551

样例 5

输入:

3
1353942 1069631319 1178682520 1916843249 4676
44630515 9075810 1377480493 1434455728 4393
55535068 1040160485 429391022 1363659343 13754

输出:

848809312519167942