TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

87.9% (29/33)

Submission's AC Ratio

33.6% (47/140)

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

Sample Input #1
3
-1 1 1

Sample Input #2
4
1 -3 2 4

Sample Output

Sample Output #1
3

Sample Output #1
6

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~35 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (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