6697.Apartments

Time Limit: 1s Memory Limit: 512MB

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 Format(From the terminal/stdin)

The first input line has three integers $n$ , $m$ , and $k$ : the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ : the desired apartment size of each applicant. If the desired size of an applicant is $x$ , they will accept any apartment whose size is between $x-k$ and $x+k$ .

The last line contains $m$ integers $b_1, b_2, \ldots, b_m$ : the size of each apartment.

  • $1 \le n, m \le 2 \cdot 10^5$
  • $0 \le k \le 10^9$
  • $1 \le a_i, b_i \le 10^9$

Output Format(To the terminal/stdout)

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

Sample Input

Copy
4 3 5
60 45 80 60
30 60 75
 · · \n
  ·  ·  ·  \n
  ·  ·  \n

Sample Output

Copy
2
 \n
Source: CSES, Sorting and Searching, 1084

Submit

请先 登录

© 2025 FAQs