Moving Points (Codeforces 1311F)
Tags: Implement, divide and conquer

There are $$$n$$$ points on a coordinate axis $$$OX$$$. The $$$i$$$-th point is located at the integer point $$$x_i$$$ and has a speed $$$v_i$$$. 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 $$$x_i + t \cdot v_i$$$.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 $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (the sum of minimum distances over all pairs of points).

Input: The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of points.The second line of the input contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^8$$$), where $$$x_i$$$ is the initial coordinate of the $$$i$$$-th point. It is guaranteed that all $$$x_i$$$ are distinct.The third line of the input contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-10^8 \le v_i \le 10^8$$$), where $$$v_i$$$ is the speed of the $$$i$$$-th point.

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


Sample Inputs:
3
1 3 2
-100 2 3

5
2 1 4 3 5
2 2 2 3 4

2
2 1
-3 0

Sample Outputs:
3

19

0

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left
string = lambda : stdin.readline().strip()
get = lambda : int(stdin.readline().strip())
array = lambda : list(map(int, stdin.readline().strip().split()))
charar = lambda : list(map(str, stdin.readline().strip()))
put = lambda *args: [stdout.write(str(i)) for i in args]
(mod, inf) = (int(1000000000.0 + 7), int(1000000000000000.0))

def solve():
    n = get()
    x = array()
    v = array()
    z = sorted(list(zip(v, x)))
    x.sort()
    s = 0
    for i in range(n):
        s += (bisect_left(x, z[i][1]) + i - n + 1) * z[i][1]
    print(s)
solve()

Solution (Python):
import operator
import collections
from sys import stdin
N = int(input())
pos = list(map(int, stdin.readline().split()))
speed = list(map(int, stdin.readline().split()))
A = []
for i in range(N):
    A.append((pos[i], speed[i]))
dist = {}
for i in pos:
    dist[i] = 0
A.sort(key=operator.itemgetter(0))
count = [0]

def merge_compare(p, r):
    if p < r:
        q = (r + p) // 2
        merge_compare(p, q)
        merge_compare(q + 1, r)
        merge(p, q, r)

def merge(p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    temp = []
    L = A[p:q + 1]
    R = A[q + 1:r + 1]
    i = 0
    j = 0
    sum_pos_right = 0
    for (e, f) in R:
        sum_pos_right += e
    while i < n_1 and j < n_2:
        if L[i][1] <= R[j][1]:
            temp.append(L[i])
            count[0] += sum_pos_right - L[i][0] * (n_2 - j)
            i += 1
        else:
            temp.append(R[j])
            sum_pos_right -= R[j][0]
            j += 1
    if i == n_1:
        temp += R[j:]
    else:
        temp += L[i:]
    A[p:r + 1] = temp
merge_compare(0, N - 1)
print(count[0])

Solution (Python):
class BIT:

    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)

    def init(self, init_val):
        for (i, v) in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i, j):
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                s += self.bit[k]
                pos += v
            v >>= 1
        return pos

    def __str__(self):
        arr = [self.sum(i, i + 1) for i in range(self.n)]
        return str(arr)
n = int(input())
X = list(map(int, input().split()))
V = list(map(int, input().split()))
Y = set(V)
Y = list(Y)
Y.sort()
toid = {}
for (i, y) in enumerate(Y):
    toid[y] = i
A = []
for (x, v) in zip(X, V):
    v = toid[v]
    A.append((x, v))
A.sort(key=lambda x: x[0])
N = len(toid)
bitCnt = BIT(N + 1)
bitSum = BIT(N + 1)
ans = 0
for (x, v) in A:
    ans += x * bitCnt.sum(0, v + 1) - bitSum.sum(0, v + 1)
    bitCnt.add(v, 1)
    bitSum.add(v, x)
print(ans)