2165 . Increa星 Array

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

93.2% (41/44)

Submission's AC Ratio

41.4% (65/157)

Tags

CKsim 2020-CKsim

Description

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

Input Format

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

1≤N≤5×105
0≤ai≤109,∀1≤i<N,ai<ai+1
1≤Q≤5×105
0≤S≤5×105

Output Format

請輸出 Q 行代表答案

Sample Input 1

3
1 2 3
5
1
2
3
4
5

Sample Output 1

1
1
2
0
1

Sample Input 2

6
0 1 4 5 7 8
3
5
12
100

Sample Output 2

3
1
0

Hints

記得不要因為輸入吃TLE

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top