問題文
在某个星球上,有一座等边三角形的城市。 N × (N + 1) / 2 房屋排列成等边三角形。该等边三角形具有一条边与东西方向平行的形状,不形成该边的顶点是最北的房子。
每栋房子都是 它们使用 2 整数进行编号。最北边的房子(1,1)从北端 i 从行西 j (1 ≦ j ≦ i ≦ N) 第房子是 (i,j)。
下面 这是 N = 5 的示例。
| (1, | 1) | ||||||||
| (2, | 1) | (2, | 2) | ||||||
| (3, | 1) | (3, | 2) | (3, | 3) | ||||
| (4, | 1) | (4, | 2) | (4, | 3) | (4, | 4) | ||
| (5, | 1) | (5, | 2) | (5, | 3) | (5, | 4) | (5, | 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 是新的 1 We are thinking of installing two radio stations to attract new customers.
如何安装广播电台 Q 建议如下。 Write a program to find the number of new customers acquired for each installation method. The
入力
输入将以以下形式通过标准输入给出。
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 行中,2 整数 编写一个程序来查找 N (1 ≦ N ≦ 1,000,000,000),M (1 ≦ M ≦ 1,000) 用空格分隔。
- 2 在 M line gives information about radio stations that have already been installed.M 行数过多 i (1 ≦ i ≦ M) 广播电台在该行 表示 i 分布的范围 给出了 3 整数 编写一个程序来查找 a_i,b_i (1 ≦ b_i ≦ a_i ≦ N),c_i (1 ≦ c_i ≦ N-a_i+1) 。 This is a radio station i 是,1 ≦ k ≦ j ≦ c_i 的整数 对于 j,k ,房子 (a_i+j-1,b_i+k-1)。 The
- M + 2 行包含一个整数 Q (1 ≦ Q ≦ 1,000) 。 来自行
- M + 3 在 Q line gives information about the new installation method.Q 行数过多 i (1 ≦ i ≦ Q) 行中,i Indicates the distribution range of the newly installed radio station in the installation method 给出了 3 整数 编写一个程序来查找 d_i,e_i (1 ≦ e_i ≦ d_i ≦ N),f_i (1 ≦ f_i ≦ N-d_i+1) 。 This is because the newly installed radio station is1 ≦ k ≦ j ≦ f_i 的整数 对于 j,k ,房子 (d_i+j-1,e_i+k-1) 预计交付。
部分点
这个问题有部分要点。 如果您正确回答所有
- N ≦ 200 以及 M ≦ 200 以及 Q ≦ 200 的数据集 如果您正确回答 1 , 您将获得10 积分。 If you answer all
- M ≦ 200 以及 Q ≦ 200 的数据集 如果您正确回答 2 correctly, you will receive 如果您正确回答所有 30 积分。 If you answer all
- 没有附加约束的数据集 3 ,您将得到以上内容 2 加上更多 获得 60 积分,总体 100 积分。 If you answer all
出力
输出是 由 Q 行组成。 输出第Q 行数过多 i (1 ≦ i ≦ Q) 行中,i 种安装方式中新分配的房屋数量。
入力例1
8 3 2 2 4 5 4 3 6 1 3 2 4 1 4 7 6 2
出力例1
5 2
已安装 3 The range of homes covered by one radio station is shown in the figure below (○ means it is being delivered, × means it is not).
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| × | ○ | ○ | ○ | |||||||||||
| × | ○ | ○ | ○ | ○ | ||||||||||
| ○ | × | × | ○ | ○ | × | |||||||||
| ○ | ○ | × | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | × | × | × |
1 第二种安装方式的情况下,新分配的房子在下图中用+表示。 5 pieces. 有一个
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| + | ○ | ○ | ○ | |||||||||||
| + | ○ | ○ | ○ | ○ | ||||||||||
| ○ | + | + | ○ | ○ | × | |||||||||
| ○ | ○ | + | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | × | × | × |
2 第二种安装方式的情况下,新分配的房子在下图中用+表示。 2 pieces. 有一个
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| × | ○ | ○ | ○ | |||||||||||
| × | ○ | ○ | ○ | ○ | ||||||||||
| ○ | × | × | ○ | ○ | × | |||||||||
| ○ | ○ | × | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | + | + | × |
入力例2
3 2 1 1 2 3 2 1 3 2 1 2 2 2 1 1 1 3
出力例2
1 0 2