No.1965 Heavier

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 :

milkcoffee / テスター :

platinum

15 ProblemId : 7894 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-05-11 23:28:41

問題文

$1$ から $N$ の番号がついた $N$ 人の人間と、同じく $1$ から $N$ の番号がついた荷物があります。
人 $i$ の体重は $A_i$ 、荷物 $i$ の重さは $B_i$ です。
$N$ 人の体重は全て異なり、体重が軽い順に番号がつけられています。すなわち、 $A_i < A_{i+1} \ (1 \leq i \leq N-1)$ が成り立ちます。

人 $i$ と人 $j$ $(i < j)$ の勝負を以下のように定義します。

人 $i$ が荷物 $i$ を、人 $j$ が荷物 $j$ をそれぞれ手に持つ。
$B_i < B_j$ であれば、お互いの手に持つ荷物を交換する。つまり、体重がより軽い方の人が、重い方の荷物を持つようにする。
自分の体重と、現在手に持っている荷物の重さの和が真に大きい方を勝ちとする。等しい場合は引き分けとする。

(1 \leq L < R \leq N)

において区間

[L,R]

が以下を満たすとき、

[L,R]

を 良い区間 であると言います。

区間内の全ての組 $(i,j) \ (L \leq i < j \leq R)$ について、人 $j$ が人 $i$ に勝つ。つまり、どの組でも体重が重い方が勝つ。

良い区間 の数を求めてください。

入力

 $N$ 
 $A_1 \ A_2 \ \dots A_N$ 
 $B_1 \ B_2 \ \dots B_N$

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_1 < A_2 < \dots < A_N \leq 10^9$
$1 \leq B_i \leq 10^9 \ (1 \leq i \leq N)$
入力は全て整数

出力

良い区間 の数を出力してください。

サンプル

サンプル1

入力

3
2 4 8
2 1 2

出力

人 $1$ と人 $2$ の勝負について、荷物は交換しません。 $A_1+B_1 < A_2+B_2$ なので人 $2$ が勝ちます。
人 $1$ と人 $3$ の勝負について、荷物は交換しません。 $A_1+B_1 < A_3+B_3$ なので人 $3$ が勝ちます。
人 $2$ と人 $3$ の勝負について、荷物を交換します。 $A_2+B_3 < A_3+B_2$ なので人 $3$ が勝ちます。

人 $2$ が人 $1$ に勝つため、区間 $[1,2]$ は 良い区間 です。
人 $3$ が人 $2$ に勝つため、区間 $[2,3]$ は 良い区間 です。
人 $2$ が人 $1$ に勝ち、人 $3$ が人 $1$ と人 $2$ に勝つため、区間 $[1,3]$ は 良い区間 です。

サンプル2

入力

2
1 10
1 1000

出力

人 $2$ は人 $1$ に勝たないため、区間 $[1,2]$ は 良い区間 ではありません。

サンプル3

入力

2
1 2
2 3

出力

人 $1$ と人 $2$ は引き分けになります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。