No.1965 Heavier
タグ : / 解いたユーザー数 83
作問者 :
milkcoffee
/ テスター :
👑 
platinum
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。