[dwango2015_prelims_5]電波局

ID: 3381

传统题

2000ms

256MiB

尝试: 0

已通过: 0

难度: 9

上传者:

admin

标签>

3300+

问题说明

有一个星球上有一个以正三角形形状排列的城市，该城市中有 $N × (N + 1) / 2$ 个房屋。这个正三角形的特点是：其中一条边平行于东西方向，并且不构成该边的顶点位于最北边的房屋。

每个房屋都用两个整数进行编号。最北边的房屋编号为 ( $1$ , $1$ )，第 $i$ 行从西到东数第 $j$ 个（ $1 ≦ j ≦ i ≦ N$ ）房屋的编号为 ( $i$ , $j$ )。

以下是 $N = 5$ 的例子：

(1,

(2,

(3,

(4,

(5,

Dwango 公司拥有 $M$ 个无线电台（编号从 $1$ 到 $M$ ），每个无线电台都向一个正三角形区域（每条边与城市外围的边平行）提供数字内容。

无线电台 $i (1 ≦ i ≦ M)$ 有 $3$ 个整数 $a_i$ 、 $b_i$ 、 $c_i$ ，并且向满足 $1 ≦ k ≦ j ≦ c_i$ 的所有整数 $j$ 、 $k$ 发送信号，将数字内容配送给房屋 ( $a_i+j-1$ , $b_i+k-1$ )。

Dwango 公司计划新建一座电视台，以吸引更多的客户。

有 $Q$ 种设立电视台的方法。请编写一个程序，对于每种设立方法，计算能够获得的新客户数量。

输入

输入是标准输入，格式如下：

$N$ $M$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ ： $a_M$ $b_M$ $c_M$ $Q$ $d_1$ $e_1$ $f_1$ $d_2$ $e_2$ $f_2$ ： $d_Q$ $e_Q$ $f_Q$

第 $1$ 行包含两个整数 $N (1 ≦ N ≦ 1,000,000,000)$ 和 $M (1 ≦ M ≦ 1,000)$ ，用空格分隔。
第 $2$ 行到第 $M$ 行提供了已经设立的无线电台的信息。其中第 $i$ 行提供了无线电台 $i$ 发出信号的范围，由 $3$ 个整数 $a_i$ 、 $b_i (1 ≦ b_i ≦ a_i ≦ N)$ 和 $c_i (1 ≦ c_i ≦ N-a_i+1)$ 组成。这表示无线电台 $i$ 向满足 $1 ≦ k ≦ j ≦ c_i$ 的所有整数 $j$ 、 $k$ 发送信号，将数字内容配送给房屋 ( $a_i+j-1$ , $b_i+k-1$ )。
第 $M+2$ 行包含一个整数 $Q (1 ≦ Q ≦ 1,000)$ 。
第 $M+3$ 行到第 $M+Q+2$ 行提供了关于新设立方法的信息。其中第 $i$ 行描述了第 $i$ 种设立方法中将要设立的无线电台发出信号的范围，由 $3$ 个整数 $d_i$ 、 $e_i (1 ≦ e_i ≦ d_i ≦ N)$ 和 $f_i (1 ≦ f_i ≦ N-d_i+1)$ 组成。这表示新设立的无线电台将向满足 $1 ≦ k ≦ j ≦ f_i$ 的所有整数 $j$ 、 $k$ 发送信号，计划将数字内容传递给房屋 ( $d_i+j-1$ , $e_i+k-1$ )。

部分得分

本问题设有部分分。

当满足 $N ≦ 200$ 且 $M ≦ 200$ 且 $Q ≦ 200$ 的数据集 $1$ 的所有测试用例均正确时，可获得 $10$ 分。
当满足 $M ≦ 200$ 且 $Q ≦ 200$ 的数据集 $2$ 的所有测试用例均正确时，除上述分数外，还可额外获得 $30$ 分。
当满足没有额外限制的数据集 $3$ 的所有测试用例均正确时，除上述分数外，还可额外获得 $60$ 分。在所有数据集上均正确将获得总共 $100$ 分。

输出

输出包含 $Q$ 行。第 $i$ 行（ $1 ≦ i ≦ Q$ ）为第 $i$ 种设立方法中所能覆盖的新房屋数量。

示例1

示例1输出

5
2

由已经建立的 $3$ 个无线电台发送的信号覆盖的房屋范围如下图所示（○表示被覆盖，×表示未被覆盖）。

○

第一种设立方法下，新增覆盖的房屋如下图中的+所示，共 $5$ 个。

○

第二种设立方法下，新增覆盖的房屋如下图中的+所示，共 $2$ 个。

○

示例2

示例2输出


1
0
2

#dwango2015prelims5. [dwango2015_prelims_5]電波局

问题说明

输入

部分得分

输出

示例1

示例1输出

示例2

示例2输出

登录