2165 . Increa星 Array

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

92.9% (39/42)

Submission's AC Ratio

43.4% (63/145)

Tags

CKsim 2020-CKsim

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 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 \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 (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