No.871 かえるのうた
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 205
作問者 : face4 / テスター : onakaT_Titai
タグ : / 解いたユーザー数 205
作問者 : face4 / テスター : onakaT_Titai
問題文最終更新日: 2019-10-05 00:12:58
問題文
直線上に$N$匹のカエルが一列に並んでいます。
左から$i(1 \leq i \leq N)$番目のカエルは位置$X_i$にいて、声の大きさは$A_i$です。
$i$番目のカエルが鳴くと閉区間$[X_i-A_i, X_i+A_i]$にその鳴き声が響きます。
カエルは他のカエルの鳴き声を聞くと共鳴します。
今、$K(1 \leq K \leq N)$番目のカエルが不意に鳴きました。
共鳴が連鎖した結果、1回以上鳴くカエルの数を求めてください。
入力
$N$ $K$ $X_1 \cdots X_N$ $A_1 \cdots A_N$
入力はすべて整数で与えられる。
- $1 \leq N \leq 10^5$
- $1 \leq K \leq N$
- $-10^{17} < X_i < 10^{17}$
- $X_1 < X_2 < \cdots < X_{N-1} < X_N$
- $0 < A_i < 10^{17}$
出力
1回以上鳴くカエルの数を出力してください。最後に改行してください。
サンプル
サンプル1
入力
5 3 -7 -1 0 4 6 6 5 4 1 7
出力
3
3番目のカエルが鳴くと、鳴き声が閉区間[-4,4]に響きます。
これを聞いて2番目のカエルと4番目のカエルが共鳴します。
2番目のカエルの鳴き声を聞いて3番目と4番目のカエルが再び共鳴し、
それを聞いて2番目と4番目が共鳴し$\cdots$と延々と鳴き続けますが、
以降他のカエルが鳴くことはありません。
2,3,4番目のカエル3匹が鳴くので、3を出力します。
サンプル2
入力
1 1 0 1000000000
出力
1
ただ鳴き声のデカいカエルが1匹鳴いただけ$\cdots$
サンプル3
入力
5 3 -1000000000000000 -11 -3 91 123 50 90 100 3 10
出力
3
入力が32bit整数型に収まらない場合があります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。