TopCoder

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

63.6% (7/11)

Tags

Description

我看著坐在前面的同學,雖然沒有很壯碩的肩膀,但看著他的背影,心中浮現一股內斂強者的霸場,像是一座山。

……不對,不只是像是,前面的同學太高了,根本就是一座山。

教室內有一排 $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]$ 。

  1. 編號 $1$ 的人前面沒有人,所以 $S_1=0$ 。
  2. $h_2+p_2=4$ ,而 $2$ 往前第一個大於 $4$ 的是 $h_1 = 5$ ,所以 $S_2 = 2 - 1 - 1 = 0$ 。
  3. $h_3+p_3=5$ ,前面沒有人的身高大於 $5$ ,所以 $S_3=2$ 。
  4. $h_4+p_4=1$ , $h_2=4>1$ ,所以 $S_4=4–2–1=1$ 。
  5. $h_5+p_5=4$ , $h_1=5>4$ ,所以 $S_5=5–1–1=3$ 。

故 $S_i$ 總和為 $6$ 。

輸入 $h$ 與 $p$ ,請計算 $\sum _ {i = 1} ^ {N} {S_i}$ 。

Input Format

輸入第一行是一個整數 $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$ 。

Output Format

輸出一行一個整數表示 $\sum _ {i = 1} ^ {N} {S_i}$ 。

Sample Input 1

5
5 4 1 1 3
0 0 4 0 1

Sample Output 1

6

Sample Input 2

10
20 1 15 17 11 2 15 3 16 3
9 14 3 14 9 16 18 4 9 6

Sample Output 2

26

Hints

Problem Source

APCS 2019/02 p4

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2