TopCoder

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

User's AC Ratio

87.5% (14/16)

Submission's AC Ratio

58.3% (28/48)

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

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