Problem7503--[CSES Problem Set] Apartments

7503: [CSES Problem Set] Apartments

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

There are $n$ applicants and $m$ free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.
Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers $n, m, k$: the number of applicants, the number of apartments, and the maximum allowed difference.
The next line contains $n$ integers $a_1,a_2,…,a_n$: the desired apartment size of each applicant. If the desired size of an applicant is $x$, he or she will accept any apartment whose size is between $x−k$ and $x+k$.
The last line contains $m$ integers $b_1,b_2,…,b_m$: the size of each apartment.

Output

Print one integer: the number of applicants who will get an apartment.

Constraints

$1 \leq n,m \leq 2 \times 10^5$
$0 \leq k \leq 10^9$
$1 \leq a_i, b_i \leq 10^9$

Sample 1 Input

4 3 5
60 45 80 60
30 60 75

Sample 1 Output

2
可用的公寓尺寸有 $60,45,80,60$ 这 $4$ 种。
第 $1$ 个申请者申请的尺寸为 $30$,因此他可以接受 $25 \sim 35$。这样没有满足要求的公寓。
第 $2$ 个申请者申请的尺寸为 $60$,因此他可以接受 $55 \sim 65$。我们可以提供尺寸为 $60$ 的公寓给申请者。
第 $3$ 个申请者申请的尺寸为 $75$,因此他可以接受 $70 \sim 80$。我们可以提供尺寸为 $80$ 的公寓给申请者。
合计有 $2$ 个申请者可以满足。

HINT

相同题目:CSES 1084

Source/Category