← 返回题目列表

AtCoder · dwango2015_prelims_5

E. 广播电台

中文机器翻译题面 查看原题

問題文

在某个星球上,有一座等边三角形的城市。 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