Codeforces Round 918 (Div. 4) |
---|
Закончено |
На числовой прямой находятся $$$n$$$ человек; $$$i$$$-й человек находится в точке $$$a_i$$$ и хочет попасть в точку $$$b_i$$$. Для каждого человека $$$a_i < b_i$$$, и начальные и конечные точки всех людей различны. (То есть все $$$2n$$$ чисел $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ различны.)
Все люди начнут двигаться одновременно со скоростью $$$1$$$ единица в секунду, пока не достигнут своей конечной точки $$$b_i$$$. Когда два человека встречаются в одной точке, они поздороваются один раз. Сколько будет приветствий?
Обратите внимание, что человек все еще может поздороваться с другими людьми, даже если они достигли своей конечной точки.
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество людей.
Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$-10^9 \leq a_i < b_i \leq 10^9$$$) — начальные и конечные позиции каждого человека.
Для каждого набора входных данных все $$$2n$$$ чисел $$$a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$$$ различны.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число, обозначающее количество приветствий, которые произойдут.
522 31 462 63 94 51 87 10-2 1004-10 10-5 5-12 12-13 135-4 9-2 53 46 78 1041 23 45 67 8
1 9 6 4 0
В первом наборе входных данных два человека встретятся в точке $$$3$$$ и поздороваются.
Название |
---|