APCS201902第4題帶著板凳排雞排的高人

https://judge.tcirc.tw/ShowProblem?problemid=d029

身高高不一定比較厲害，個子矮的如果帶板凳可能會變高。有 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)。計算可得 h(i)+p(i)=(5,4,5,1,4)，編號 1 的人前面沒有人，所以 1 的最大可挑戰人數 S(1)=0。

對編號 2 的人而言，h(2)+p(2)=4，而往前看到第一個大於 4 的是h(1)=5，所以S(2)=2–1–1=0。

而 h(3)+p(3)=5 ，前面沒有人的身高大於 5，所以 S(3)=2。

而 h(4)+p(4)=1， h(2)=4>1，所以位置 2 是 4 的無法超越位置，S(4)=4–2–1=1。

同理可求出 S(5)=3，他的不可超越位置是 1 的身高 5。輸入 h() 與 p()，請計算所有人 S(i) 的總和。

輸入說明

第一行為 n，n≤2e5；第二行有 n 個正整數，依序是 h(1)~h(n)；第三行有 n 個非負整數，依序代表是 p(1)~p(n)；數值都不超過 10^7，同一行數字之間都是以空白間隔。

輸出說明

輸出 S(i) 的總和。答案可能超過 2^32，但不會超過 2^60。

輸入範例1

5 4 1 1 3

0 0 4 0 1

輸出範例1

解題策略

map與upper_bound