- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
روی محور اعداد، \(n\) بازه داریم. هر بازه به یکی از ۸ حالت زیر است:
- نوع ۱. \((a, \infty)\) مجموعه همهی اعداد بزرگتر از \(a\) است.
- نوع ۲. \((-\infty, a)\) مجموعه همهی اعداد کوچکتر از \(a\) است.
- نوع ۳. \([a, \infty)\) مجموعه همهی اعداد بزرگتر یا مساوی \(a\) است.
- نوع ۴. \((-\infty, a]\) مجموعه همهی اعداد کوچکتر یا مساوی \(a\) است.
- نوع ۵. \((a, b)\) مجموعه همهی اعداد بزرگتر از \(a\) و کوچکتر از \(b\) است.
- نوع ۶. \((a, b]\) مجموعه همهی اعداد بزرگتر از \(a\) و کوچکتر یا مساوی \(b\) است.
- نوع ۷. \([a, b)\) مجموعه همهی اعداد بزرگتر یا مساوی \(a\) و کوچکتر از \(b\) است.
- نوع ۸. \([a, b]\) مجموعه همهی اعداد بزرگتر یا مساوی \(a\) و کوچکتر یا مساوی \(b\) است.
به شما \(n\) بازه که به یکی از ۸ حالت بالا است داده میشود. از شما میخواهیم اجتماع این \(n\) بازه را به روش استاندارد نمایش دهید.
منظور از نمایش استاندارد یعنی تعدادی بازه ناتهی از ۸ حالت بالا انتخاب کنید و پشت سرهم بنویسید به طوری که هیچ دوتایی اشتراک نداشته باشند. برای کنار هم گذاشتن دو بازه از نماد U (اجتماع) استفاده کنید. (برای بهتر متوجه شدن خواستهی سوال، به مثالها توجه کنید.)
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(n\) آمده که تعداد بازهها را نشان میدهد.
\[1 \leq n \leq 100\, 000\]
در \(n\) سطر بعدی، در هر سطر یک بازه از ۸ نوع معرفی شده به شما نمایش داده میشود. تضمین میشود بازههای داده شده درست و ناتهی هستند. مقدار بینهایت (\(\infty\)) در ورودی به صورت inf نمایش داده میشود.
تمامی اعداد حاضر در ورودی کوچکتر مساوی \(10^9\) هستند.
| زیرمسئله | امتیاز |
|---|---|
| \(n \leq 500\) | ۵۰ |
| بدون محدودیت اضافه | ۵۰ |
خروجی
اجتماع این بازهها را به روش استاندارد چاپ کنید. دقت کنید بازههای خروجی باید مرتب باشند.
مثال
ورودی نمونه ۱
3
[-3, -1)
(-2, 2)
(4, 5]
خروجی نمونه ۱
[-3, 2) U (4, 5]
ورودی نمونه ۲
3
(-inf, 3)
(3, 7)
[7, inf)
خروجی نمونه ۲
(-inf, 3) U (3, inf)
ورودی نمونه ۳
2
(1, 2)
[2, 3)
خروجی نمونه ۳
(1, 3)
ورودی نمونه ۴
2
(1, 2)
(2, 3)
خروجی نمونه ۴
(1, 2) U (2, 3)