| Codeforces Round 573 (Div. 1) |
|---|
| Закончено |
Дано $$$n$$$ точек на плоскости, $$$i$$$-я из которых расположена в $$$(x_i, y_i)$$$. Tokitsukaze хочет нарисовать странную прямоугольную область и взять все точки в этой области.
Странная область ограничена тремя прямыми, $$$x = l$$$, $$$y = a$$$ и $$$x = r$$$, это ее левая, нижняя и правая сторона, соответственно, где $$$l$$$, $$$r$$$ и $$$a$$$ могут являться любыми вещественными числами, удовлетворяющими $$$l < r$$$. Верхняя сторона области неограничена, то есть можно считать, что она ограничена прямой, параллельной оси $$$x$$$, и бесконечно удаленной. Странная прямоугольная область изображена на следующей иллюстрации.
Точка $$$(x_i, y_i)$$$ находится в странной прямоугольной области тогда и только тогда, когда $$$l < x_i < r$$$ и $$$y_i > a$$$. К примеру, на иллюстрации выше $$$p_1$$$ находится в области, а $$$p_2$$$ — нет.
Tokitsukaze хочет узнать, сколько существует различных непустых множеств, которые можно получить, выбирая все точки в некоторой странной прямоугольной области. Два множества считаются различными, если существует хотя бы одна точка в одном из них, которой нет во втором.
В первой строке записано единственное число $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$) — количество точек на плоскости.
В $$$i$$$-й из следующих $$$n$$$ строк записаны два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 10^9$$$) — координаты $$$i$$$-й точки.
Гарантируется, что все точки различные.
Выведите единственное целое число — количество различных непустых множеств точек, которые она может получить.
3
1 1
1 2
1 3
3
3
1 1
2 1
3 1
6
4
2 1
2 2
3 1
3 2
6
В первом примере существует только одно множество, содержащее $$$k$$$ точек для $$$k = 1, 2, 3$$$, поэтому общее число множеств равно $$$3$$$.
Во втором примере количества множеств размера $$$k$$$ для $$$k = 1, 2, 3$$$ равны $$$3$$$, $$$2$$$, $$$1$$$ соответственно, и их сумма равна $$$6$$$.
В третьем примере, как показывает следующая иллюстрация, есть
- $$$2$$$ множества из одной точки;
- $$$3$$$ множества из двух точек;
- $$$1$$$ множество из четырех точек.
Исходя из этого, количество различных непустых множеств в этом примере равно $$$2 + 3 + 0 + 1 = 6$$$.
