Account
GitHubFeedback
Drafts and results saved on this device
Submit on CSES.fi
CSES Problemset/Sorting and Searching

Apartments

#1084
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

Time limit:1.00 s
Memory limit:512 MB
Unsolved
Download Tests (.zip)

There are nn applicants and mm 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 nn, mm, and kk: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n: the desired apartment size of each applicant. If the desired size of an applicant is xx, they will accept any apartment whose size is between x−kx-k and x+kx+k.

The last line contains mm integers b1,b2,…,bmb_1, b_2, \ldots, b_m: the size of each apartment.

Output

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

Constraints
  • 1≤n,m≤2⋅1051 \le n, m \le 2 \cdot 10^5
  • 0≤k≤1090 \le k \le 10^9
  • 1≤ai,bi≤1091 \le a_i, b_i \le 10^9
Sample Test Cases (1)
Example 1ID: sample-1
Input
4 3 5
60 45 80 60
30 60 75
Expected Output
2
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|1 line, 0 chars
Test Bench
Download .zip
Input (stdin)
4 3 5
60 45 80 60
30 60 75
Expected Output
2