题目描述
Salma 想给墙上的粘土马赛克上色。该马赛克由
为了给马赛克上色,Salma 首先选取两个长度为
然后她重复以下步骤直至所有瓷砖都上色完成:
她找到任意一片没有上色的瓷砖
可以证明,瓷砖最终的颜色不依赖于 Salma 的上色顺序。
Yasmin 对马赛克瓷砖的颜色非常好奇。她向 Salma 提出
问题的答案是该长方形中黑色瓷砖的数量。具体来说,Salma 应当找出有多少片瓷砖
请编写程序回答 Yasmin 的问题。
实现细节
你要实现以下函数。
std::vector<long long> mosaic( std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R)
, :长度为 的数组,分别描述最上方行和最左边列的瓷砖的颜色。 , , , :长度为 的数组,分别描述 Yasmin 所提出的问题。- 该函数应返回一个长度为
的数组 ,使得 给出问题 ( )的答案。 - 对每个测试用例,该函数恰好被调用一次。
约束条件
- 对所有满足
的 ,都有 ,且 - 对所有满足
的 ,都有 ,且
子任务
子任务 | 分数 | 额外的约束条件 |
---|---|---|
1 | ||
2 | ||
3 | 对所有满足 |
|
4 | ||
5 | 对所有满足 |
|
6 | 对所有满足 |
|
7 | 对所有满足 |
|
8 | 没有额外的约束条件。 |
例子
考虑以下函数调用。
mosaic([1, 0, 1, 0], [1, 1, 0, 1], [0, 2], [3, 3], [0, 0], [3, 2])
该例子如下图所示。左边的图展示了马赛克中瓷砖的颜色,中间和右边的图分别展示了 Yasmin 的第一个问题和第二个问题中的长方形。
这两个问题的答案(即阴影长方形中 1 的个数)分别是 7 和 3。因此,函数应该返回
评测程序示例
输入格式:
N X[0] X[1] ... X[N-1] Y[0] Y[1] ... Y[N-1] Q T[0] B[0] L[0] R[0] T[1] B[1] L[1] R[1] ... T[Q-1] B[Q-1] L[Q-1] R[Q-1]
输出格式:
C[0] C[1] ... C[S-1]
其中 mosaic
所返回的数组
时间限制:
空间限制: