7503: [CSES Problem Set] Apartments
[Creator : ]
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.
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.
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$
$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$ 个申请者可以满足。
第 $1$ 个申请者申请的尺寸为 $30$,因此他可以接受 $25 \sim 35$。这样没有满足要求的公寓。
第 $2$ 个申请者申请的尺寸为 $60$,因此他可以接受 $55 \sim 65$。我们可以提供尺寸为 $60$ 的公寓给申请者。
第 $3$ 个申请者申请的尺寸为 $75$,因此他可以接受 $70 \sim 80$。我们可以提供尺寸为 $80$ 的公寓给申请者。
合计有 $2$ 个申请者可以满足。