79 . 潮汐區間

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Cheng0928
NLOJ 管理員，題目若有誤請至 Discord 私訊我！

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

37.5% (3/8)

Tags

Description

海岸有一座古老的觀測塔，塔頂的水晶每日都會記錄海流的波動。
某一天，觀測塔收到了連續 $n$ 份潮汐紀錄，第 $i$ 份紀錄的數值為 $a_i$。這些數值有時代表漲潮，有時代表退潮，也可能因為風暴而出現劇烈起伏。

海岸守望者相信，只要某一段連續時間內的潮汐總變化落在 $L$ 到 $R$ 之間，這段時間就足以視為「適合通航」的安全時段。
因此，他們希望你幫忙找出：在這 $n$ 份紀錄之中，有多少段連續區間的總和介於 $L$ 與 $R$ 之間。

對於所有測試資料：
$1 \le n \le 2 \times 10$$5$
$-10$$18$ $\le L \le R \le 10$$18$
$-10$$9$ $\le a_i \le 10$$9$

Input Format

共輸入兩行，
第一行輸入三個數字 $n,\ L,\ R$，
第二行輸入 $n$ 個數字，第 $i$ 個數字為 $a_i$。

Output Format

輸出一個數字代表答案。

Sample Input 1

5 3 12
1 -4 6 -2 6

Sample Output 1

8

Sample Input 2

5 -6 13
4 9 2 1 3

Sample Output 2

11

Sample Input 3

5 3 3
9 -6 9 10 7

Sample Output 3

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測試資料 0
2 0~16 $n \le 100$ 5
3 0~30 $n \le 1000$ 10
4 1, 31~44 $0 \le a_i$ 35
5 2, 45~58 $L = R$ 35
6 0~72 無額外限制 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3 6
1 1000 65536 65536 1 2 3 4 6
2 1000 65536 65536 1 2 3 5 6
3 1000 65536 65536 2 3 6
4 1000 65536 65536 2 3 6
5 1000 65536 65536 2 3 6
6 1000 65536 65536 2 3 6
7 1000 65536 65536 2 3 6
8 1000 65536 65536 2 3 6
9 1000 65536 65536 2 3 6
10 1000 65536 65536 2 3 6
11 1000 65536 65536 2 3 6
12 1000 65536 65536 2 3 6
13 1000 65536 65536 2 3 6
14 1000 65536 65536 2 3 6
15 1000 65536 65536 2 3 6
16 1000 65536 65536 2 3 6
17 1000 65536 65536 3 6
18 1000 65536 65536 3 6
19 1000 65536 65536 3 6
20 1000 65536 65536 3 6
21 1000 65536 65536 3 6
22 1000 65536 65536 3 6
23 1000 65536 65536 3 6
24 1000 65536 65536 3 6
25 1000 65536 65536 3 6
26 1000 65536 65536 3 6
27 1000 65536 65536 3 6
28 1000 65536 65536 3 6
29 1000 65536 65536 3 6
30 1000 65536 65536 3 6
31 1000 65536 65536 4 6
32 1000 65536 65536 4 6
33 1000 65536 65536 4 6
34 1000 65536 65536 4 6
35 1000 65536 65536 4 6
36 1000 65536 65536 4 6
37 1000 65536 65536 4 6
38 1000 65536 65536 4 6
39 1000 65536 65536 4 6
40 1000 65536 65536 4 6
41 1000 65536 65536 4 6
42 1000 65536 65536 4 6
43 1000 65536 65536 4 6
44 1000 65536 65536 4 6
45 1000 65536 65536 5 6
46 1000 65536 65536 5 6
47 1000 65536 65536 5 6
48 1000 65536 65536 5 6
49 1000 65536 65536 5 6
50 1000 65536 65536 5 6
51 1000 65536 65536 5 6
52 1000 65536 65536 5 6
53 1000 65536 65536 5 6
54 1000 65536 65536 5 6
55 1000 65536 65536 5 6
56 1000 65536 65536 5 6
57 1000 65536 65536 5 6
58 1000 65536 65536 5 6
59 1000 65536 65536 6
60 1000 65536 65536 6
61 1000 65536 65536 6
62 1000 65536 65536 6
63 1000 65536 65536 6
64 1000 65536 65536 6
65 1000 65536 65536 6
66 1000 65536 65536 6
67 1000 65536 65536 6
68 1000 65536 65536 6
69 1000 65536 65536 6
70 1000 65536 65536 6
71 1000 65536 65536 6
72 1000 65536 65536 6
Submit
Back to Top