- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون نهایی سوم دوره ۲۶ المپیاد کامپیوتر
در تورنمنت جهانی «نانبیار، کبابببر»، ورزشکاران با قدرت دستهایشان شناخته میشوند. در این مسابقات، \(n\) ورزشکار شرکت کردهاند که قدرت دست راست ورزشکار \(i\)-ام، \(r_i\) و قدرت دست چپش \(l_i\) است. در این مسابقات، در هر مرحله، مسابقهای بین دو ورزشکار انجام میشود و فرد بازنده از تورنمنت حذف میشود. بنابراین بعد از \(n-1\) مرحله، تنها یک فرد در تورنمنت باقی میماند که مدال طلای مسابقات را دریافت میکند.
اگر مسابقهای بین ورزشکار \(i\) و \(j\) انجام شود، ورزشکار \(i\) شانس پیروزی در این مسابقه را دارد اگر \(l_i > r_j\) و یا \(r_i > l_j\) باشد.
برنامهای بنویسید که با گرفتن قدرت دستهای ورزشکاران، ورزشکارانی را که شانس کسب مدال طلای مسابقات را دارند، پیدا کند.
ورودی
در خط اول ورودی عدد طبیعی \(n\)، تعداد ورزشکاران، آمده است. در هر یک از \(n\) خط بعدی، قدرت دستهای ورزشکاران آمده است. در خط \(i\) از این خطوط، به ترتیب دو عدد طبیعی \(r_i\) و \(l_i\) آمده است که نشاندهندهی قدرت دست راست و دست چپ ورزشکار \(i\) است. تضمین میشود تمامی \(l_i\)ها و \(r_i\)ها متمایز هستند.
\[1\leq n \leq 200\ 000\] \[1\leq l_i, r_i\leq 2 \times n\]
خروجی
در تنها خط خروجی یک رشتهی \(n\) حرفی از 0 و 1 چاپ کنید که 1 بودن حرف \(i\)ام این رشته نشاندهندهی این است که ورزشکار \(i\)ام شانس قهرمانی دارد.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۲ | \(n\le 20\) |
| ۲ | ۱۶ | \(n\le 200\) |
| ۳ | ۲۸ | \(n \le 2\ 000\) |
| ۴ | ۴۴ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
2
1 2
3 4
خروجی نمونه ۱
01
ورودی نمونه ۲
4
1 8
6 7
5 4
3 2
خروجی نمونه ۲
1111