← 返回题目列表

Codeforces · 1311/F

F. 移动点

中文机器翻译题面 查看原题

坐标轴 $$$OX$$$ 上有 $$$n$$$ 个点。第 $$$i$$$ 个点位于整数点 $$$x_i$$$ 处,速度为 $$$v_i$$$。保证没有两个点占据相同的坐标。所有$$$n$$$点匀速移动,$$$t$$$时刻第$$$i$$$点的坐标($$$t$$$可以是非整数)计算为$$$x_i + t \cdot v_i$$$。

考虑两个点 $$$i$$$ 和 $$$j$$$。令 $$$d(i, j)$$$ 为在任何可能的时刻(甚至非整数)内这两点之间的最小可能距离。这意味着如果两个点 $$$i$$$ 和 $$$j$$$ 在某个时刻重合,则值 $$$d(i, j)$$$ 将是 $$$0$$$。

您的任务是计算值 $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (所有点对的最小距离之和)。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 点数。

输入的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^8$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个点的初始坐标。保证所有 $$$x_i$$$ 都是不同的。

输入的第三行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$-10^8 \le v_i \le 10^8$$$),其中 $$$v_i$$$ 是第 $$$i$$$ 个点的速度。

输出

打印一个整数 — 值 $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (所有点对的最小距离之和)。

示例

输入 #1

3
1 3 2
-100 2 3

输出 #1

3

输入 #2

5
2 1 4 3 5
2 2 2 3 4

输出 #2

19

输入 #3

2
2 1
-3 0

输出 #3

0