分数: 100 点
问题陈述
JOI-Garden 呈矩形,分为网格 H 行和 W 列。 该单元格位于 i从顶部开始的第行和 j从左边算起的第列称为单元格 (i,j).
当雨水落在某个单元格上时,该单元格的湿度会增加。 除了下雨的时候,细胞的湿度水平永远不会改变。 如果细胞的水分含量至少达到 X,细胞变成泥浆,这是危险的。 因此,每天早上,JOI花园的管理者JOI君最多可以指定一个矩形禁区,其中包含湿度至少为1的所有细胞。 X。 更准确地说,JOI君选择了四个整数 u,d,l,r (1\leq u\leq d\leq H,1\leq l\leq r\leq W),以及由所有单元格组成的矩形区域 (i,j) 满意 u\leq i\leq d 和 l\leq j\leq r 变为禁区。
最初,JOI 花园中每个单元的湿度为 0.
从今天开始,每天晚上都会下雨一次,持续时间 N 天。 当天晚上 (k - 1)(之后的第天1\leq k\leq N),雨落在每个细胞上 (i,j) 满意 U_k\leq i\leq D_k 和 L_k\leq j\leq R_k,每个这样的电池的湿度水平增加 C_k.
对于每个 k=1,2,\ldots ,N,编写一个程序,计算 JOI-kun 在当天早上设置的禁区中包含的最小可能的单元格数量 k之后的第三天。
输入
从标准输入读取以下数据。
H W N X U_1 D_1 L_1 R_1 C_1 U_2 D_2 L_2 R_2 C_2 \vdots U_N D_N L_N R_N C_N
输出
写 N 行到标准输出。 的 输出的 k- 第行 (1 \leq k \leq N)应包含 JOI-kun 在当天早上设置的禁区中包含的最小可能数量的单元格 k.
约束
- 1 \leq H \leq 10^9.
- 1 \leq W \leq 10^9.
- 1 \leq N \leq 200\,000.
- 1 \leq X \leq 2\times 10^{14}.
- 1 \leq U_k \leq D_k \leq H (1 \leq k \leq N).
- 1 \leq L_k \leq R_k \leq W (1 \leq k \leq N).
- 1 \leq C_k \leq 10^9 (1 \leq k \leq N).
- 给定值均为整数。
子任务
- (3 点) X = 1.
- (24 点) W = 1.
- (15 点) N \leq 300.
- (30 点) N \leq 5\,000.
- (28 点)没有额外的限制。
示例输入 1
3 3 5 10 3 3 1 1 5 1 3 1 2 7 1 3 3 3 4 1 1 1 2 12 3 3 3 3 6
示例输出 1
0 1 1 6 9
以下是湿度水平如何每天增加以及如何选择禁区以使所含细胞数量最小化的一个示例。
- 当天晚上 0,电池的湿度水平 (3,1) 增加 5。 当天早上 1,没有任何细胞的水分含量至少为 10,因此没有设置禁区。
- 当天晚上 1,细胞的湿度水平 (1,1), (1,2), (2,1), (2,2), (3,1),和 (3,2) 每增加 7。 当天早上 2,细胞 (3,1) 的水分含量至少为 10。 JOI君选择 u=d=3 和 l=r=1,从而设置一个禁区,其中包含 1 细胞。
- 当天晚上 2,细胞的湿度水平 (1,3), (2,3),和 (3,3) 每增加 4。 当天早上 3,细胞 (3,1) 的水分含量至少为 10。 JOI君选择 u=d=3 和 l=r=1,从而设置一个禁区,其中包含 1 细胞。
- 当天晚上 3,细胞的湿度水平 (1,1),和 (1,2) 每增加 12。 当天早上 4,细胞 (1,1),(1,2),和 (3,1) 的水分含量至少为 10。 JOI君选择 u=1, d=3, l=1, r=2,从而设置一个禁区,其中包含 6 细胞。
- 当天晚上 4,电池的湿度水平 (3,3) 增加 6。 当天早上 5,细胞 (1,1), (1,2), (3,1),和 (3,3) 的水分含量至少为 10。 JOI君选择 u=1, d=3, l=1, r=3,从而设置一个禁区,其中包含 9 细胞。
此示例输入满足子任务 3、4 和 5 的约束。
示例输入 2
9 1 5 1 3 3 1 1 4 5 8 1 1 1 3 5 1 1 3 8 8 1 1 4 8 9 1 1 5
示例输出 2
1 6 6 6 7
此示例输入满足所有子任务的约束。
示例输入 3
4596 9794 15 141929907 600 3070 2222 8763 472026497 47 2644 3276 6033 930213777 638 945 304 1100 992702990 370 2211 2178 2977 783902937 277 2601 1559 8989 842013671 566 3272 3124 8456 254633541 91 4241 2655 8035 303526265 1342 3662 3909 7175 685435928 1176 4012 2827 8429 614977118 255 2461 1482 5835 794902067 982 2314 941 3952 342731056 1603 2215 6730 7105 332440107 2301 4568 6898 9561 591652619 124 2097 3520 8882 168525684 1845 3599 5592 7145 555656973
示例输出 3
16165282 19783008 25583040 25583040 26266464 28021036 36437770 36437770 36437770 36437770 36437770 36437770 41864676 41864676 41864676
此示例输入满足子任务 3、4 和 5 的约束。