問題一覧 > 通常問題

No.871 かえるのうた

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 205
作問者 : face4face4 / テスター : onakaT_TitaionakaT_Titai
19 ProblemId : 3119 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。