No.871 かえるのうた

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 110
作問者 : face4face4 / テスター : onakaT_TitaionakaT_Titai
7 ProblemId : 3119 / 出題時の順位表

問題文

直線上に$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整数型に収まらない場合があります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。