No.871 Song of the Frogs
タグ : / 解いたユーザー数 212
作問者 :
face4
/ テスター :
onakaT_Titai
Problem Statement
$N$ frogs are lined up in a row on a straight line.
The $i(1 \leq i \leq N)$-th frog from the left is at position $X_i$, and its voice loudness is $A_i$.
When the $i$-th frog croaks, its croak echoes over the closed interval $[X_i-A_i, X_i+A_i]$.
A frog resonates when it hears the croak of another frog.
Now, the $K(1 \leq K \leq N)$-th frog has suddenly croaked.
Find the number of frogs that croak at least 1 time as a result of the chain of resonance.
Input
$N$ $K$ $X_1 \cdots X_N$ $A_1 \cdots A_N$
All input values are integers.
- $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}$
Output
Output the number of frogs that croak at least 1 time. Print a newline at the end.
Sample
Sample 1
Input
5 3 -7 -1 0 4 6 6 5 4 1 7
Output
3
When the 3rd frog croaks, its croak echoes over the closed interval [-4,4].
Hearing this, the 2nd frog and the 4th frog resonate.
Hearing the 2nd frog's croak, the 3rd and 4th frogs resonate again,
and hearing that, the 2nd and 4th frogs resonate, and $\cdots$ so they keep croaking endlessly,
but no other frog ever croaks after that.
Since the 3 frogs numbered 2, 3, 4 croak, output 3.
Sample 2
Input
1 1 0 1000000000
Output
1
Just 1 frog with a really loud voice croaked, that's all$\cdots$
Sample 3
Input
5 3 -1000000000000000 -11 -3 91 123 50 90 100 3 10
Output
3
The input may not fit in a 32-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。