Kotlin Heroes: Episode 1 |
---|
Закончено |
Задано $$$n$$$ отрезков на координатной оси $$$Ox$$$. $$$i$$$-й отрезок задан парой $$$l_i, r_i$$$, где $$$l_i$$$ равно позиции левого конца $$$i$$$-го отрезка, а $$$r_i$$$ равно позиции правого конца $$$i$$$-го отрезка. Отрезки могут пересекаться, вкладываться и даже совпадать. Отрезок — это множество чисел (включая вещественнозначные) которые находятся между концами отрезка или совпадают с ними. Формально, отрезок $$$[l, r]=\{x~|~x \in \Bbb{R},~l \le x \le r\}$$$.
Назовем объединением отрезков все точки оси, покрытые набором отрезков. Назовем подмножество заданных отрезков хорошим, если его объединение равно объединению всех $$$n$$$ отрезков.
Ваша задача — посчитать количество хороших подмножеств заданных $$$n$$$ отрезков. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество отрезков.
Следующие $$$n$$$ строк содержат отрезки. $$$i$$$-й отрезок задан парой $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$), где $$$l_i$$$ равно левой границе отрезка, а $$$r_i$$$ равно правой границе отрезка. Отрезки могут пересекаться, вкладываться и даже совпадать.
Выведите количество хороших подмножеств заданного множества отрезков. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.
3 1 1 2 6 1 6
4
2 3 4 2 5
2
4 1 2 5 5 2 3 1 3
5
Название |
---|