QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
统计

数轴上有 $n$ 个黑点,坐标为 $a[]$;$n$ 个白点,坐标为 $b[]$(下标均从 $0$ 开始)。同时你有两个参数 $l_a$ 和 $l_b$,满足 $n \geq 2$ 且 $1 \leq l_b < l_a$。注意同一个位置可能有多个点。

你需要找到一个 $0$ 到 $n-1$ 的排列 $p[]$,满足对于所有 $i$,有 $a[i] \leq b[p[i]] \leq a[i] + l_a$。你需要最大化满足 $b[p[i]] \leq a[i] + l_b$ 的下标 $i$ 的个数。数据保证存在一个合法的排列。

输入格式

第一行,三个正整数 $n$,$l_a$,$l_b$。

接下来一行,$n$ 个正整数,表示 $a[]$。

接下来一行,$n$ 个正整数,表示 $b[]$。

输出格式

输出一行一个非负整数,表示满足条件的下标个数。

样例数据

样例输入

3 5 1
1 2 5
4 6 7

样例输出

1

样例解释

$n=3$,$l_a=5$,$l_b=1$

$a[] = \{1, 2, 5\}$

$b[] = \{4, 6, 7\}$

一种最好的排列是 $p[] = \{0, 2, 1\}$,$b[p[2]] = b[1] = 6$ 和 $a[2] = 5$ 的差不超过 $l_b = 1$,其他均不满足这个条件,答案为 $1$。

$p[] = \{2, 0, 1\}$ 不是合法的排列,因为 $b[2] = 7$ 被 $a[0] = 1$ 匹配,它们的差为 $6$,超过了 $l_a = 5$。

$p[] = \{1, 2, 0\}$ 不是合法的排列,因为 $b[0] = 4$ 被 $a[2] = 5$ 匹配,但不满足 $b[0] \geq a[2]$。

$p[] = \{0, 1, 2\}$ 虽然是合法的排列,但是答案为 $0$,不是最优解。

子任务

子任务 1(4 分):满足 $n \leq 10$。

子任务 2(14 分):满足 $n \leq 100$。

子任务 3(37 分):满足 $n \leq 5\,000$。

子任务 4(16 分):满足 $l_a = 5 \times 10^5$。

子任务 5(29 分):无特殊限制。

对于所有数据,$2 \leq n \leq 5 \times 10^5$,$1 \leq a[i], b[i] \leq 5 \times 10^5$,$1 \leq l_b \leq l_a \leq 5 \times 10^5$。保证存在一个合法的排列。