G - 1D Country 解説 /

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

配点 : 350 点

問題文

数直線上に N 個の村があります。i 番目の村は座標 X_i にあり、P_i 人の村人がいます。

Q 個のクエリに答えてください。i 番目のクエリは以下の形式です。

  • 整数 L_i,R_i が与えられる。座標が L_i 以上 R_i 以下の村に住んでいる村人の人数の総数を求めよ。

制約

  • 1\leq N,Q\leq 2\times 10^5
  • -10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
  • 1\leq P_i\leq 10^9
  • -10^9\leq L_i \leq R_i \leq 10^9
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 \ldots X_N
P_1 \ldots P_N
Q
L_1 R_1
\vdots
L_Q R_Q

出力

Q 行出力せよ。

i\ (1\leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

4
1 3 5 7
1 2 3 4
4
1 1
2 6
0 10
2 2

出力例 1

1
5
10
0

1 番目のクエリについて考えます。座標が 1 以上 1 以下の村は、座標 1 にある村で、村人は 1 人います。よって答えは 1 です。

2 番目のクエリについて考えます。座標が 2 以上 6 以下の村は、座標 3 にある村と座標 5 にある村で、村人はそれぞれ 2 人と 3 人います。よって答えは 2+3=5 です。

入力例 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

出力例 2

26
15
7
26
18
28
26
11

Score : 350 points

Problem Statement

There are N villages on a number line. The i-th village is located at coordinate X_i, and has P_i villagers.

Answer Q queries. The i-th query is in the following format:

  • Given integers L_i and R_i, find the total number of villagers living in villages located between coordinates L_i and R_i, inclusive.

Constraints

  • 1\leq N,Q\leq 2\times 10^5
  • -10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
  • 1\leq P_i\leq 10^9
  • -10^9\leq L_i \leq R_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
X_1 \ldots X_N
P_1 \ldots P_N
Q
L_1 R_1
\vdots
L_Q R_Q

Output

Print Q lines.

The i-th line(1\leq i \leq Q) should contain the answer to the i-th query.

Sample Input 1

4
1 3 5 7
1 2 3 4
4
1 1
2 6
0 10
2 2

Sample Output 1

1
5
10
0

Consider the first query. The villages between coordinates 1 and 1 are the village at coordinate 1, with 1 villager. Hence, the answer is 1.

Consider the second query. The villages between coordinates 2 and 6 are the villages at coordinates 3 and 5, with 2 and 3 villagers, respectively. Hence, the answer is 2+3=5.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2

26
15
7
26
18
28
26
11