Codeforces Round 624 (Div. 3) |
---|
Закончено |
На координатной оси $$$OX$$$ находятся $$$n$$$ точек. $$$i$$$-я точка располагается в целочисленной координате $$$x_i$$$ и имеет скорость $$$v_i$$$. Гарантируется, что никакие две точки не располагаются в одной и той же координате. Все $$$n$$$ точек двигаются с неизменной скоростью, координата $$$i$$$-й точки в момент времени $$$t$$$ ($$$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)$$$ (суммы минимальных дистанций по всем парам точек).
3 1 3 2 -100 2 3
3
5 2 1 4 3 5 2 2 2 3 4
19
2 2 1 -3 0
0
Название |
---|