CF1311F.Moving Points

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are nn points on a coordinate axis OXOX. The ii-th point is located at the integer point xix_i and has a speed viv_i. It is guaranteed that no two points occupy the same coordinate. All nn points move with the constant speed, the coordinate of the ii-th point at the moment tt (tt can be non-integer) is calculated as xi+t⋅vix_i + t \cdot v_i.

Consider two points ii and jj. Let d(i,j)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 ii and jj coincide at some moment, the value d(i,j)d(i, j) will be 00.

Your task is to calculate the value ∑1≤i<j≤n\sum\limits_{1 \le i \lt j \le n} d(i,j)d(i, j) (the sum of minimum distances over all pairs of points).

在坐标轴 OXOX 上有 nn 个点。第 ii 个点位于整数坐标 xix_i 处,且具有速度 viv_i。保证任意两个点不占据相同的坐标。所有 nn 个点均以恒定速度运动;在时刻 tt(tt 可为非整数)时,第 ii 个点的坐标为 xi+t⋅vix_i + t \cdot v_i。

考虑两个点 ii 和 jj。令 d(i,j)d(i, j) 表示这两个点在任意时刻(包括非整数时刻)可能达到的最小距离。换言之,若点 ii 和点 jj 在某一时刻重合,则 d(i,j)=0d(i, j) = 0。

你的任务是计算 ∑1≤i<j≤nd(i,j)\sum\limits_{1 \le i \lt j \le n} d(i, j)(即所有点对的最小距离之和)。

输入格式

The first line of the input contains one integer nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5) — the number of points.

The second line of the input contains nn integers x1,x2,…,xnx_1, x_2, \dots, x_n (1≤xi≤1081 \le x_i \le 10^8), where xix_i is the initial coordinate of the ii-th point. It is guaranteed that all xix_i are distinct.

The third line of the input contains nn integers v1,v2,…,vnv_1, v_2, \dots, v_n (−108≤vi≤108-10^8 \le v_i \le 10^8), where viv_i is the speed of the ii-th point.

输入的第一行包含一个整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5)—— 表示点的数量。

输入的第二行包含 nn 个整数 x1,x2,…,xnx_1, x_2, \dots, x_n(1≤xi≤1081 \le x_i \le 10^8),其中 xix_i 表示第 ii 个点的初始坐标。保证所有 xix_i 互不相同。

输入的第三行包含 nn 个整数 v1,v2,…,vnv_1, v_2, \dots, v_n(−108≤vi≤108-10^8 \le v_i \le 10^8),其中 viv_i 表示第 ii 个点的速度。

输出格式

Print one integer — the value ∑1≤i<j≤n\sum\limits_{1 \le i \lt j \le n} d(i,j)d(i, j) (the sum of minimum distances over all pairs of points).

输出一个整数——即 ∑1≤i<j≤nd(i,j)\sum\limits_{1 \le i \lt 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

输入解题思路,AI测评打分。不知道怎么写?

首页