[R54E]二元组和四元组 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给你一个长度为 $n$ 的整数序列 $a$ 和一个长度为 $m$ 的整数序列 $b$，下标从 $1$ 开始，保证 $a$ 和 $b$ 严格单调递增，即对于所有 $i$（$1 \le i < n$），满足 $a_i < a_{i+1}$ 且对于所有 $j$（$1 \le j < m$），满足 $b_j < b_{j+1}$。

对于一个整数二元组 $(x,y)$，定义其权值为四元组 $(i,j,k,l)$ 的个数，满足 $a_i \le x < a_j$ 且 $b_k \le y < b_l$。

给你一个正整数 $v$，请你输出权值至少为 $v$ 的二元组 $(x,y)$ 的个数。

格式

输入格式

第一行包含三个整数 $n,m,v$，分别表示序列 $a$ 的长度、序列 $b$ 的长度和题目描述中的参数。

接下来一行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示序列 $a$。

接下来一行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$，表示序列 $b$。

输出格式

输出一行一个整数，表示权值至少为 $v$ 的二元组 $(x,y)$ 的个数。

样例

样例输入 #1

2 4 2
1 3
2 4 6 7

样例输出 #1

10

样例解释 #1

权值至少为 $2$ 的二元组分别为：

$(1,2)$，权值为 $3$。

$(1,3)$，权值为 $3$。

$(1,4)$，权值为 $4$。

$(1,5)$，权值为 $4$。

$(1,6)$，权值为 $3$。

$(2,2)$，权值为 $3$。

$(2,3)$，权值为 $3$。

$(2,4)$，权值为 $4$。

$(2,5)$，权值为 $4$。

$(2,6)$，权值为 $3$。

样例输入 #2

3 5 11
-3 -1 4
-2 0 1 3 4

样例输出 #2

21

数据规模

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

子任务编号	分数	$n,m \le$	$\lvert a_i \rvert,\lvert b_i \rvert \le$
$1$	$10$	$10$	$40$
$2$	$10$	$40$	$100$
$3$	$20$	$500$	$500$
$4$	$30$	$3000$	$10^9$
$5$	$30$	$2 \times 10^5$

对于 $100\%$ 的数据：$1 \le n,m \le 2 \times 10^5$，$1 \le v \le 10^{18}$，$-10^9 \le a_1 < a_2 < \dots < a_n \le 10^9$，$-10^9 \le b_1 < b_2 < \dots < b_m \le 10^9$。