← 返回题目列表

AtCoder · awc0016_d

D. 搬运行李的路径

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

分数: 366 分

问题陈述

高桥是一位来访的送货员 N 仓库排列成一排,按顺序收集包裹。仓库都有编号 1, 2, \ldots, N 从西到东,还有仓库 i 包含一包重量 A_i.

高桥从某个仓库开始 s (1 \leq s \leq N)没有携带任何包裹,向东依次访问仓库。每次他访问仓库时,他都会在那里拿起包裹并将其添加到他的货物中。他保留了他收到的所有包裹。

具体来说,在每个仓库,他都遵循以下步骤:

  1. 在那个仓库拿起包裹并将其添加到他的负载中。
  2. 检查他的货物总重量(包括刚刚拿起的包裹)。
  3. 如果总重量大于 K (即超过 K),高桥无法继续前进并停在该仓库。
  4. 如果总重量最多为 K 且当前仓库不是仓库 N,他移动到下一个仓库(东边的邻近仓库)并返回到步骤 1。
  5. 如果总重量最多为 K 且当前仓库为仓库 N,东边已经没有仓库了,所以他停在了那个仓库。

也就是说,从仓库出发时 s,高桥参观仓库 s, s+1, s+2, \ldots 有序,并停在仓库 t 其中累计包裹重量 A_s + A_{s+1} + \cdots + A_t 首先超过 K。如果他到达仓库 N 超出无 K,他停在仓库 N.

定义 f(s) 为Takahashi停靠的仓库编号。

高桥想回答 Q 问题。 j第一个问题,整数 给出了表示起始点范围的 L_j, R_j 。求出 的值 f(L_j) + f(L_j + 1) + \cdots + f(R_j).

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 所有输入值均为整数。

输入

N K Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含仓库数量 N,总重量上限 K,以及问题数量 Q,用空格分隔。
  • 第二行包含每个仓库的包裹重量 A_1, A_2, \ldots, A_N,用空格分隔。
  • 以下 Q 行每条都包含起点范围 每个问题的 L_j, R_j ,用空格分隔。

输出

打印 Q 行。上 j第行,打印答案 j第一个问题,即值 f(L_j) + f(L_j + 1) + \cdots + f(R_j).


示例输入 1

5 10 3
3 4 2 5 1
1 5
1 3
3 5

示例输出 1

23
13
15

示例输入 2

4 5 2
3 3 3 3
1 4
2 3

示例输出 2

13
7

示例输入 3

10 15 4
5 3 7 2 8 1 4 6 9 3
1 10
3 7
1 1
5 10

示例输出 3

78
39
4
56

示例输入 4

15 20 5
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5
1 15
5 10
1 5
10 15
8 12

示例输出 4

164
62
35
90
67

示例输入 5

1 1000000000000000 1
1
1 1

示例输出 5

1