在 22 世紀,哆啦 A 夢是日本警視廳的警視總監,他奉命要調查在太平洋第 7 島鏈上面的勢力,進行武力分析。
哆啦 A 夢派出了小哆啦去調查島鏈上面的小島,這個島鏈上共有 $N$ 個小島,並且對每個小島進行武力分析,得知每個小島的武力值。
這些小島分成兩種派系,一派是支持大雄、一派是支持胖虎,哆啦 A 夢為了保護大雄避免胖虎的欺負,所以想先分析島鏈上有多少個區間,火拼時大雄會輸。
區間火拼:
則計算區間中大雄派的武力值總和與胖虎派武力值總和,若胖虎派武力值總和大於大雄派武力值總和則大雄派輸。
「我不在的時候你能夠好好照顧自己嗎?」哆啦 A 夢邊生氣邊流淚地問大雄。
每筆測資只有一組資料
第一行為一個正整數 $N$ ($1 \leq N \leq 2 \cdot10^5$),代表島鏈上面的小島數量。
第二行共有 $N$ 個整數 $a_i$ ($1 \leq |a_i| \leq 10^5$),$\lvert a_i\rvert$ 為小島的武力值,當 $a_i > 0$ 則為大雄派 ,反之則為胖虎派。
輸出一個整數,代表島鏈上有多少個區間,火拼時大雄派會輸。
在第一個範例中,小島都是支持大雄,所以大雄沒有輸。
在第二個範例中,共有 13 個區間大雄會輸,分別為:
$[2, 2]$, $[4, 4]$, $[5, 5]$,
$[1, 2]$, $[2, 3]$, $[3, 4]$, $[4, 5]$,
$[1, 3]$, $[2, 4]$, $[3, 5]$,
$[1, 4]$, $[2, 5]$,
$[1, 5]$
以區間 $[1, 4]$ 為例,支持大雄的武力值總和為 $1021+1516=2537$、支持胖虎的武力值總和為 $5009+8002=13011$,因為 $2537 < 13011$,所以這個區間大雄輸。
reference: NHDK Moon Festival Ten Point Round 2021
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~4 | $N \leq$ $10$ | 0 |
2 | 0~9 | 無特別限制 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 |