TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

92.2% (71/77)

Submission's AC Ratio

32.0% (131/409)

Tags

Description

現在還是雲端大數據物聯網的時代,社群網站上無時無刻仍然有著海量的廢文被發表。

這次,你手上的資料換成了全球網路廢文資料集(data set),試圖從中得到珍貴的資訊。

你在茫茫廢文海中發現了一個使用者 — Eddy — 所發的廢文特別有深意,在數位的時代,他所發的所有廢文被編碼成了一串整數 $a_1,a_2,\ldots,a_n$。第 $i$ 個整數代表 Eddy 在第 $i$ 天所發的廢文。數字的大小有它的意義,當我們看了一篇被編碼成數字 $x$ 的廢文之後,我們心靈的正面能量值會加上 $x$。當正面能量值掉到小於 $0$ 時,我們會變得內心扭曲,言行不得體,毀家廢婚,面容猥瑣,這是很不好的事情。

為了大家好,你想要檢查 Eddy 所發的廢文會不會造成社會道德危機。我們在看一個人發的廢文時,常常都是從某一則廢文開始,照著發表時間一篇一篇看,看到不想看為止。我們可以定義「看法」為一組 $(l, r)$,代表依序把 $a_l,a_{l+1},\ldots,a_r$ 這幾篇廢文看過。而「不道德」的看法則是在觀看廢文的過程中,會有某些時刻使得起始正面能量值為$0$的人內心扭曲。例如 Eddy 發了 $100, -300, 200, 400$ 這幾篇廢文,那 $(3, 4)$ 是一組道德的看法 (觀看 $200, 400$ 的過程中正面能量值總是不小於 $0$),$(1, 4)$ 則是不道德的看法,因為看完第 2 篇時正面能量值為 $-200$,這是內心扭曲的證據。

你想要知道,Eddy 所發的廢文,有幾種不道德的看法。

Input Format

測試資料共包含兩行。
第一行有一個正整數 $n$,表示 Eddy 所發的廢文數量。第二行有 $n$ 個以空格隔開的整數,第 $i$ 個數字 $a_i$ 表示 Eddy 於第 $i$ 天所發的廢文。

  • 所有 $a_i$ 皆滿足 $-100000 \leq a_i \leq 100000$
  • $1\leq n\leq 10^ 6$

Output Format

輸出一行包含一個非負整數,代表 Eddy 廢文裡不道德看法的數量。

Sample Input 1

3
-1 1 1

Sample Output 1

3

Sample Input 2

4
1 -3 2 4

Sample Output 2

6

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~35 100

Testdata and Limits

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