CF1311F.Moving Points
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are n points on a coordinate axis OX. The i-th point is located at the integer point xi and has a speed vi. It is guaranteed that no two points occupy the same coordinate. All n points move with the constant speed, the coordinate of the i-th point at the moment t (t can be non-integer) is calculated as xi+t⋅vi.
Consider two points i and j. Let d(i,j) be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points i and j coincide at some moment, the value d(i,j) will be 0.
Your task is to calculate the value 1≤i<j≤n∑ d(i,j) (the sum of minimum distances over all pairs of points).
在坐标轴 OX 上有 n 个点。第 i 个点位于整数坐标 xi 处,且具有速度 vi。保证任意两个点不占据相同的坐标。所有 n 个点均以恒定速度运动;在时刻 t(t 可为非整数)时,第 i 个点的坐标为 xi+t⋅vi。
考虑两个点 i 和 j。令 d(i,j) 表示这两个点在任意时刻(包括非整数时刻)可能达到的最小距离。换言之,若点 i 和点 j 在某一时刻重合,则 d(i,j)=0。
你的任务是计算 1≤i<j≤n∑d(i,j)(即所有点对的最小距离之和)。
输入格式
The first line of the input contains one integer n (2≤n≤2⋅105) — the number of points.
The second line of the input contains n integers x1,x2,…,xn (1≤xi≤108), where xi is the initial coordinate of the i-th point. It is guaranteed that all xi are distinct.
The third line of the input contains n integers v1,v2,…,vn (−108≤vi≤108), where vi is the speed of the i-th point.
输入的第一行包含一个整数 n(2≤n≤2⋅105)—— 表示点的数量。
输入的第二行包含 n 个整数 x1,x2,…,xn(1≤xi≤108),其中 xi 表示第 i 个点的初始坐标。保证所有 xi 互不相同。
输入的第三行包含 n 个整数 v1,v2,…,vn(−108≤vi≤108),其中 vi 表示第 i 个点的速度。
输出格式
Print one integer — the value 1≤i<j≤n∑ d(i,j) (the sum of minimum distances over all pairs of points).
输出一个整数——即 1≤i<j≤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
输入解题思路,AI测评打分。不知道怎么写?