[R50D]三元组2 - 代码源竞赛平台

时空限制

1S/512M

给定三个数组 $a, b, c$ ，它们的长度分别为 $n_a, n_b, n_c$ ，另外给定一个非负整数 $d$ 。

请你求出有多少个三元组 $(i, j, k)$ 满足以下两个条件：

这里 $1 \leq i \leq n_a$ ， $1 \leq j \leq n_b$ ， $1 \leq k \leq n_c$ 。

第一行包含四个整数 $n_a, n_b, n_c, d$ ，分别表示数组 $a, b, c$ 的长度以及给定的数 $d$ 。

第二行包含 $n_a$ 个整数 $a_1, a_2, \dots, a_{n_a}$ ，表示数组 $a$ 的值。

第三行包含 $n_b$ 个整数 $b_1, b_2, \dots, b_{n_b}$ ，表示数组 $b$ 的值。

第四行包含 $n_c$ 个整数 $c_1, c_2, \dots, c_{n_c}$ ，表示数组 $c$ 的值。

输出一行一个整数，表示满足条件的三元组 $(i, j, k)$ 的数量。

在这个样例中， $n_a=2, n_b=2, n_c=2, d=2$ 。我们需要寻找满足 $a_i \leq b_j \leq c_k$ 且 $c_k - a_i \leq 2$ 的三元组 $(i, j, k)$ ：

$(1, 1, 1)$ ： $a_1=1, b_1=2, c_1=3$ 。满足 $1 \leq 2 \leq 3$ ，且 $3 - 1 = 2 \leq 2$ 。
$(1, 2, 1)$ ： $a_1=1, b_2=3, c_1=3$ 。满足 $1 \leq 3 \leq 3$ ，且 $3 - 1 = 2 \leq 2$ 。
$(1, 1, 2)$ ： $a_1=1, b_1=2, c_2=4$ 。满足 $1 \leq 2 \leq 4$ ，但 $4 - 1 = 3 > 2$ ，不满足。
$(1, 2, 2)$ ： $a_1=1, b_2=3, c_2=4$ 。满足 $1 \leq 3 \leq 4$ ，但 $4 - 1 = 3 > 2$ ，不满足。
$(2, 1, 1)$ ： $a_2=2, b_1=2, c_1=3$ 。满足 $2 \leq 2 \leq 3$ ，且 $3 - 2 = 1 \leq 2$ 。
$(2, 2, 1)$ ： $a_2=2, b_2=3, c_1=3$ 。满足 $2 \leq 3 \leq 3$ ，且 $3 - 2 = 1 \leq 2$ 。
$(2, 1, 2)$ ： $a_2=2, b_1=2, c_2=4$ 。满足 $2 \leq 2 \leq 4$ ，且 $4 - 2 = 2 \leq 2$ 。
$(2, 2, 2)$ ： $a_2=2, b_2=3, c_2=4$ 。满足 $2 \leq 3 \leq 4$ ，且 $4 - 2 = 2 \leq 2$ 。

共有 $6$ 个三元组满足条件，因此输出 6。

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n_a, n_b, n_c\le$	子任务依赖
$1$	$40$	$200$	无
$2$	$60$	$2\times 10^5$	$1$

对于 $100\%$ 的数据， $1 \leq n_a, n_b, n_c \leq 2 \times 10^5$ ， $0 \leq d \leq 10^9$ ， $1 \leq a_i, b_j, c_k \leq 10^9$ 。