← 返回题目列表

AtCoder · tkppc3_d

D. 巨型棋盘

中文机器翻译题面 查看原题
配点: 400 点

問題文

ZRK 你收到了RKZ先生送给你的生日棋盘。棋盘是垂直的。 H 方形 * 水平 W 它是一个网格,所有边都与外框平行或垂直。从顶部 i 行,从左起 j 标记列中的方块 (i, j) 。还有,棋盘上的方格 (1, 1) 为黑色,相邻的方块被涂上不同的颜色,如下图所示。

然而,棋盘上的方格大小是扭曲的,从上往下看 i 该行中所有单元格的高度为 a_i,从左起 j 列中的所有单元格具有相同的宽度。 b_j 。 (详情请参考下图。)

ZRK 收到了有缺陷的商品,他说:“左上角的方块是 (px, py) 右下方块是 包含在 (qx, qy) 的矩形中,(黑色矩形的总面积)-(白色矩形的总面积)'' Q 我决定通过玩一个提问游戏来平静自己的心情。为愤怒的ZRK寻求答案。


以下是, 这是 a_1=7, a_2=35, a_3=5, b_1=14, b_2=9, b_3=50 情况下的棋盘图。


入力

输入是按以下格式从标准输入给出的。 输出超过

H W Q
a_1 a_2 a_3 ... a_H
b_1 b_2 b_3 ... b_W
px_1 py_1 qx_1 qy_1
px_2 py_2 qx_2 qy_2
px_3 py_3 qx_3 qy_3
...
px_Q py_Q qx_Q qy_Q

出力

Q 行。

i 在该行中,左上角的方块是 (px_i, py_i),右下方块是 打印(黑色矩形的总面积)- (qx_i, qy_i) 矩形中包含的(白色矩形的总面积)。 是小于或等于

制約

  • H, W, Q 是 给出了 1 以上 100 \ 000 的整数。
  • a_i, b_i 是 给出了 1 以上 10 \ 000 的整数。
  • px_i, qx_i 是 给出了 1 以上 H 的整数。
  • py_i, qy_i 是 给出了 1 以上 W 的整数。
  • px_i \leq qx_i, py_i \leq qy_i 。

小課題

小課題1 [ 30点 ]

  • H, W \leq 1 \ 000 很满意。
  • Q \leq 5 很满意。

小課題2 [ 120点 ]

  • H, W \leq 1 \ 000 很满意。

小課題3 [ 250点 ]

  • 没有其他限制。

入力例1

3 3 2
7 35 5
14 9 50
1 1 2 2
1 1 3 2

出力例1

-140
-115

这是问题文本中的图像示例。

例如, 1 第二题,黑色部分的面积为 (7 * 14) + (9 * 35) = 413 白色部分的面积是 (7 * 9) + (14 * 35) = 553 。 (黑色部分的总面积) - (白色部分的总面积) = 413 - 553 = -140 。

入力例2

5 5 5
1 6 15 15 7
14 11 11 5 14
3 5 5 5
2 3 3 4
1 5 3 5
4 3 4 4
2 2 4 3

出力例2

98
54
140
-90
0

作者: 亮2016