TopCoder

Thumb 2021 06 15 09 47 58 %e7%9a%84%e8%9e%a2%e5%b9%95%e6%93%b7%e5%9c%96
FHVirus
$\Huge{せやな                        ⋊}$

User's AC Ratio

92.9% (26/28)

Submission's AC Ratio

32.0% (32/100)

Tags

Description

對於一個序列,假如你從左邊看到右邊看到的數字嚴格的越來越大,我們說他是Increa星的序列
給你一個Increa星的序列 $\langle a_i \rangle$
接著有 $Q$ 筆詢問
每筆詢問是一個 $S$ ,問你有多少個區間總和恰好是 $S$

Input Format

第一行有一個正整數 $N$ 代表序列的長度
第二行有 $N$ 個非負整數 $a_i$
第三行有一個正整數 $Q$
接下來 $Q$ 行,每行有一個非負整數 $S$

$1 \leq N \leq 5 \times 10^ 5$
$0 \leq a_i \leq 10^ 9, \forall 1 \leq i < N, a_i < a_{i+1}$
$1 \leq Q \leq 5 \times 10^ 5$
$0 \leq S \leq 5 \times 10^ 5$

Output Format

請輸出 $Q$ 行代表答案

Sample Input

Sample Input 1
3
1 2 3
5
1
2
3
4
5

Sample Input 2
6
0 1 4 5 7 8
3
5
12
100

Sample Output

Sample Output 1
1
1
2
0
1

Sample Output 2
3
1
0

Hints

記得不要因為輸入吃TLE

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N \leq 20, Q \leq 100, S \leq 100$ 10
2 5~14 $N \leq 2000$ 10
3 15~19 $Q \leq 5$ 10
4 20~24 $S \leq 2000$ 10
5 0~39 無其他限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 700 524288 65536 1 5
1 700 524288 65536 1 5
2 700 524288 65536 1 5
3 700 524288 65536 1 5
4 700 524288 65536 1 5
5 700 524288 65536 2 5
6 700 524288 65536 2 5
7 700 524288 65536 2 5
8 700 524288 65536 2 5
9 700 524288 65536 2 5
10 700 524288 65536 2 5
11 700 524288 65536 2 5
12 700 524288 65536 2 5
13 700 524288 65536 2 5
14 700 524288 65536 2 5
15 700 524288 65536 3 5
16 700 524288 65536 3 5
17 700 524288 65536 3 5
18 700 524288 65536 3 5
19 700 524288 65536 3 5
20 700 524288 65536 4 5
21 700 524288 65536 4 5
22 700 524288 65536 4 5
23 700 524288 65536 4 5
24 700 524288 65536 4 5
25 700 524288 65536 5
26 700 524288 65536 5
27 700 524288 65536 5
28 700 524288 65536 5
29 700 524288 65536 5
30 700 524288 65536 5
31 700 524288 65536 5
32 700 524288 65536 5
33 700 524288 65536 5
34 700 524288 65536 5
35 700 524288 65536 5
36 700 524288 65536 5
37 700 524288 65536 5
38 700 524288 65536 5
39 700 524288 65536 5