e047: 帶著板凳排雞排的高人
Tags :
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-01-15 23:01

Content

身高高不一定比較厲害,個子矮的如果帶板凳可能會變高。有 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)的總和。

Input

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

Output

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

Sample Input
5
5 4 1 1 3
0 0 4 0 1
Sample Output
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
出處:
AP325 [管理者:
Eason0165 (EasonLearner)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」