← 返回题目列表

AtCoder · joi2024_yo2_b

B. 购物2

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

配点: 100 点

問題文

JOI商店 有 N 个产品,产品包括 它们的编号最大为 1 它们的编号最大为 N 。

每个产品包括:定価和種類已定义。产品展示 i (1 \leqq i \leqq N) 的标价为 P_i 这是一个圆圈。产品类型是 1 以上 M 用下面的整数表示,乘积 i (1 \leqq i \leqq N)类型是 A_i 。从

JOI Shop 决定进行促销。销售是 M 持续数天,j 日目 (1 \leqq j \leqq M) 是类型 您可以以正常价格的一半购买所有 j 产品。

促销期间,Q 顾客参观了JOI商店。对于客户 它们的编号最大为 1 它们的编号最大为 Q 。顾客 k (1 \leqq k \leqq Q)正在销售。 T_k 当天参观了JOI商店并购买了产品。 L_k, L_k+1, \dots, R_k 的 1 我一件一件地买了。

为了调查销售效果,我想知道每个客户购买产品所花费的金额。

给定产品信息和客户信息,编写一个程序来计算每个客户购买该产品所需的金额。

制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq M\leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • 2 \leqq P_i \leqq 10^9 (1 \leqq i \leqq N).
  • P_i 是偶数 (1 \leqq i \leqq N).
  • 1 \leqq A_i \leqq M (1 \leqq i \leqq N).
  • 1 \leqq T_k \leqq M (1 \leqq k \leqq Q).
  • 1 \leqq L_k \leqq R_k \leqq N (1 \leqq k \leqq Q).
  • 所有输入值都是整数。

小課題

  1. (15 点) N \leqq 2\,000,M \leqq 2\,000,Q \leqq 2\,000.
  2. (20 点) M = 1.
  3. (12 点) M \leqq 10.
  4. (14 点) A_i \neq A_j (1 \leqq i < j \leqq N).
  5. (22 点) P_i = 2 (1 \leqq i \leqq N).
  6. (17 点)没有额外的限制。

入力

输入按以下格式给出。 输出

N M Q
P_1 A_1
P_2 A_2
\vdots
P_N A_N
T_1 L_1 R_1
T_2 L_2 R_2
\vdots
T_Q L_Q R_Q

出力

Q 行。k 行目 (1 \leqq k \leqq Q) 有一位客户 输出购买该产品所需花费的金额 k ,省略单位(日元)。 购买该产品的费用为


入力例 1

5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5

出力例 1

45
50
75

客 1 购买该产品所需的金额为 40 \div 2 + 30 \div 2 + 20 \div 2 = 45 由于是日元,1 在线 一个整数,表示住在 45 。 准备

客 2 购买该产品所需的金额为 30 \div 2 + 20 \div 2 + 50 \div 2 = 50 由于是日元,2 在线 一个整数,表示住在 50 。 准备

客 3 购买该产品所需的金额为 10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75 由于是日元,3 在线 一个整数,表示住在 75 。 准备

此输入示例是一个小作业。 1,2,3,6 满足约束。


入力例 2

5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5

出力例 2

80
75
135

客 1 购买该产品所需的金额为 40 + 30 + 20 \div 2 = 80 由于是日元,1 在线 一个整数,表示住在 80 。 准备

客 2 购买该产品所需的金额为 30 + 20 + 50 \div 2 = 75 由于是日元,2 在线 一个整数,表示住在 75 。 准备

客 3 购买该产品所需的金额为 10 + 40 + 30 \div 2 + 20 + 50 = 135 由于是日元,3 在线 一个整数,表示住在 135 。 准备

此输入示例是一个小作业。 1,3,6 满足约束。


入力例 3

5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4

出力例 3

85
170
50

此输入示例是一个小作业。 1,3,4,6 满足约束。


入力例 4

10 5 4
2 1
2 5
2 4
2 3
2 4
2 2
2 2
2 4
2 2
2 1
3 2 7
1 1 7
2 1 10
5 5 8

出力例 4

11
13
17
8

此输入示例是一个小作业。 1,3,5,6 满足约束。


入力例 5

10 10 10
741703628 7
231838922 5
920286164 3
763741914 5
246151406 7
54109256 1
966457488 5
441379880 10
458514202 2
224373612 1
5 5 10
2 2 7
1 9 9
1 3 4
9 4 6
1 1 7
9 4 7
4 8 8
7 5 9
1 4 5

出力例 5

1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320

此输入示例是一个小作业。 1,3,6 满足约束。