問題一覧 > 通常問題

No.1965 Heavier

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 : milkcoffeemilkcoffee / テスター : platinumplatinum
12 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
出力
3

人 $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
出力
0

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

サンプル3
入力
2
1 2
2 3
出力
0

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

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