D - 荷物運びの道 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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 を順に訪れ、累積の荷物の重量 A_s + A_{s+1} + \cdots + A_t が初めて K より大きくなった倉庫 t で止まります。K を超えることなく倉庫 N まで到達した場合は倉庫 N で止まります。

高橋君が止まった倉庫の番号を f(s) と定義します。

高橋君は 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
  • 1 行目には、倉庫の数 N 、荷物の合計重量の上限 K 、質問の数 Q が、スペース区切りで与えられる。
  • 2 行目には、各倉庫の荷物の重さ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から 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

Score : 366 pts

Problem Statement

Takahashi is a delivery worker who visits N warehouses arranged in a row, collecting packages in order. The warehouses are numbered 1, 2, \ldots, N from west to east, and warehouse i contains a package of weight A_i.

Takahashi starts at some warehouse s (1 \leq s \leq N) carrying no packages, and visits warehouses sequentially heading east. Each time he visits a warehouse, he picks up the package there and adds it to his load. He keeps all packages he has picked up.

Specifically, at each warehouse, he follows these steps:

  1. Pick up the package at that warehouse and add it to his load.
  2. Check the total weight of his load (including the package just picked up).
  3. If the total weight is greater than K (i.e., exceeds K), Takahashi cannot proceed further and stops at that warehouse.
  4. If the total weight is at most K and the current warehouse is not warehouse N, he moves to the next warehouse (the neighboring warehouse to the east) and returns to step 1.
  5. If the total weight is at most K and the current warehouse is warehouse N, there are no more warehouses to the east, so he stops at that warehouse.

In other words, when starting from warehouse s, Takahashi visits warehouses s, s+1, s+2, \ldots in order, and stops at warehouse t where the cumulative package weight A_s + A_{s+1} + \cdots + A_t first exceeds K. If he reaches warehouse N without exceeding K, he stops at warehouse N.

Define f(s) as the number of the warehouse where Takahashi stops.

Takahashi wants to answer Q questions. In the j-th question, integers L_j, R_j representing a range of starting points are given. Find the value of f(L_j) + f(L_j + 1) + \cdots + f(R_j).

Constraints

  • 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)
  • All input values are integers.

Input

N K Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains the number of warehouses N, the upper limit on total weight K, and the number of questions Q, separated by spaces.
  • The second line contains the weights of packages at each warehouse A_1, A_2, \ldots, A_N, separated by spaces.
  • The following Q lines each contain the range of starting points L_j, R_j for each question, separated by spaces.

Output

Print Q lines. On the j-th line, print the answer to the j-th question, namely the value of f(L_j) + f(L_j + 1) + \cdots + f(R_j).

Sample Input 1

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

Sample Output 1

23
13
15

Sample Input 2

4 5 2
3 3 3 3
1 4
2 3

Sample Output 2

13
7

Sample Input 3

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

Sample Output 3

78
39
4
56

Sample Input 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

Sample Output 4

164
62
35
90
67

Sample Input 5

1 1000000000000000 1
1
1 1

Sample Output 5

1