eolymp
bolt
Try our new interface for solving problems
Məsələlər

Олексій та відрізки

Олексій та відрізки

\textbf{Зверніть увагу, що вам суворо заборонено порушувати правила олімпіади. Тобто, обговорювати з іншими ці задачі, поширювати розв'язки, просити допомоги, тощо. На Всеукраїнській олімпіаді з програмування ми дискваліфікували понад 200 учасників. Якщо ви будете порушувати правила - ви також будете дискваліфіковані.} Олексій дуже любить порожні перетини. Так, сьогодні він отримав $n$ відрізків, що розташовані на одній прямій. Тепер він зацікавився, скільки існує трійок відрізків, що не перетинаються між собою. Допоможіть Олексієві знайти це число. Вважається, що два відрізки не перетинаються, якщо правий кінець одного з них розташований лівіше (має строго меншу координату), ніж лівий кінець іншого. \InputFile Перший рядок містить одне ціле число $n$ ($3 \leq n \leq 2 \cdot 10^5$) --- кількість відрізків, що розташовані на одній прямій. Наступні $n$ рядків містять по два цілі числа $l_i$ та $r_i$ ($1 \leq l_i < r_i \leq 10^9$) --- координати лівого та правого кінців $i$-го відрізка. \OutputFile Виведіть єдине число --- кількість трійок $i < j < k$ таких, що відрізки під цими номерами не перетинаються між собою. \Note У першому тесті три відрізки перетинаються в точці з координатою $7$, тому ця трійка не підходить.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
1 5
7 20
6 7
Çıxış verilənləri #1
0
Giriş verilənləri #2
6
5 15
3 4
10 12
7 8
1 9
15 16
Çıxış verilənləri #2
5
Müəllif Andrey Abdulaev