我看著坐在前面的同學,雖然沒有很壯碩的肩膀,但看著他的背影,心中浮現一股內斂強者的霸場,像是一座山。
……不對,不只是像是,前面的同學太高了,根本就是一座山。
教室內有一排 $n$ 個人的座位,由前往後從 $1$ 到 $N$ 編號,第 $i$ 個人坐下時的身高為 $h_i$ ,而且帶了高度為 $p_i$ 的座墊。若 $j$ 排在 $i$ 之前且 $j$ 的身高大於 $i$ 加了座墊的高度,也就是 $h_j > h_i + p_i$,則我們說 $j$ 是 $i$ 的「大山」。若 $j$ 是 $i$ 最後面的大山,則兩人之間的人數 $i−j−1$ 稱為第 $i$ 個人和山的距離 $S_i$ 。
如果第 $i$ 個人沒有「大山」,則山的距離 $S_i = i-1$ ,也就是排在他之前全部的人數。
舉例來說,假設 $N=5$,身高 $h$ 依序為 $[5,4,1,1,3]$ 而座墊的高度 $p$ 依序是 $[0,0,4,0,1]$ 。
故 $S_i$ 總和為 $6$ 。
輸入 $h$ 與 $p$ ,請計算 $\sum _ {i = 1} ^ {N} {S_i}$ 。
輸入第一行是一個整數 $N$。
第二行有 $N$ 個正整數 $h_1 \sim h_N$ 。
第二行有 $N$ 個非負整數 $p_1 \sim p_N$ 。
輸入保證 $1\le N\le 2 \cdot 10^ 5$,$1\le h_i \le 10 ^ 9, 0 \le p_i \le 10^ 9$ 。
輸出一行一個整數表示 $\sum _ {i = 1} ^ {N} {S_i}$ 。
APCS 2019/02 p4
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~23 | 無額外限制 | 100 |