فهرست مندرجات
Stylist
آرایشگر تنبل قصه‌ی ما، ﻫﺮ ﺭﻭﺯ ﺣﺪﺍﮐﺜﺮ ﯾﮏ ﻣﺸﺘﺮﯼ ﺭﺍ ﺁﺭﺍﯾﺶ ﻣﯽﮐﻨﺪ. ﺍﻭ ﻫﺮ ﺭﻭﺯﯼ ﮐﻪ ﺑﯿﮑﺎﺭ ﻣﯽﺷﻮﺩ، ﺑﻪ ﻣﺴﺎﻓﺮﺕ ﻣﯽﺭﻭﺩ ﻭ ﺗﺎ ﻭﻗﺘﯽ ﻣﺸﺘﺮﯼ ﺩﯾﮕﺮﯼ ﻧﺒﺎﺷﺪ، ﺑﺎﺯ ﻧﻤﯽﮔﺮﺩﺩ. ﺷﻮﻫﺮ ﺍﻭ ﺍﺯ ﺍﯾﻦ ﻣﻮﺿﻮﻉ ﺑﺴﯿﺎﺭ ﻧﺎﺭﺍﺣﺖ ﺍﺳﺖ ﻭ ﻣﯽﺧﻮﺍﻫﺪ ﻃﻮﺭﯼ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﮐﻨﺪ ﮐﻪ ﺯﻧﺶ ﮐﻢ ﺑﻪ ﻣﺴﺎﻓﺮﺕ ﺑﺮﻭﺩ. ﺍﻭ ﺍﺯ ﺗﻤﺎﻣﯽ ﻣﺸﺘﺮﯾﻬﺎﯼ ﻫﻤﺴﺮ، بازه‌ی ﺯﻣﺎﻧﯽﺍﯼ ﮐﻪ ﻣﯽﺧﻮﺍﻫﻨﺪ ﺩﺭ ﺁﻥ ﺑﻪ ﺁﺭﺍﯾﺸﮕﺎﻩ ﺑﺮﻭﻧﺪ، ﺭﺍ ﮔﺮﻓﺘﻪ ﻭ ﺣﺎﻻ ﺑﻪ ﺩﻧﺒﺎﻝ ﺗﻌﯿﯿﻦ روز ﺯ ﺁﺭﺍﯾﺶ ﻫﺮ ﻣﺸﺘﺮﯼ ﺍﺳﺖ ﻃﻮﺭﯼ ﮐﻪ ﺗﻌﺪﺍﺩ ﻣﺴﺎﻓﺮﺗﻬﺎﯼ ﺁﺭﺍﯾﺸﮕﺮ، کم‌ترین ﻣﻘﺪﺍﺭ ﻣﻤﮑﻦ ﺷﻮﺩ. ﺷﻮﻫﺮ ﺁﺭﺍﯾﺸﮕﺮ ﻭﻗﺘﯽ ﺑﺎﺯﻩﻫﺎﯼ ﺗﻤﺎﻡ ﻣﺸﺘﺮﯼﻫﺎ ﺭﺍ ﭘﺮﺳﯿﺪ، ﻣﺘﻮﺟﻪ ﺷﺪ ﮐﻪ ﻫﯿﭻ ﺑﺎﺯﻩﺍﯼ ﺑﺮﺍﺑﺮ ﺑﺎ ﺩﯾﮕﺮﯼ ﻭ ﯾﺎ ﺷﺎﻣﻞ ﺁﻥ ﻧﯿﺴﺖ. ﺍﻭ ﺍﺯ ﻫﻤﯿﻦ ﻣﻮﺿﻮﻉ ﻣﺘﻮﺟﻪ ﺷﺪ ﮐﻪ ﻣﯽﺗﻮﺍﻥ ﻃﻮﺭﯼ ﺗﻤﺎﻣﯽ ﻣﺸﺘﺮﯼﻫﺎ ﺭﺍ ﺗﻌﯿﯿﻦ ﻭﻗﺖ ﮐﺮﺩ ﮐﻪ ﻫﻤﺴﺮﺵ همه‌ی آن‌ها ﺭﺍ ﺁﺭﺍﯾﺶ ﮐﻨﺪ ﻭ ﻣﺠﺒﻮﺭ ﻧﺸﻮﺩ ﺩﺭ ﯾﮏ ﺭﻭﺯ ﺩﻭ ﻣﺸﺘﺮﯼ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ.
ﺷﻤﺎ ﺑﺎﯾﺪ ﺑﺮ ﺍﺳﺎﺱ ﺑﺎﺯﻩﺍﯼ ﮐﻪ ﻫﺮ ﻣﺸﺘﺮﯼ ﻣﯽﺧﻮﺍﻫﺪ ﺩﺭ ﺁﻥ ﺁﺭﺍﯾﺶ ﺷﻮﺩ، ﺍﯾﻦ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﺭﺍ ﺑﺮﺍﯼ شوهر بیچاره‌ی آرایشگر ﺍﻧﺠﺎﻡ ﺩﻫﯿﺪ. ﻫﺮ ﻣﺸﺘﺮﯼ ﺑﺎﯾﺪ ﺩﻗﯿﻘﺎً ﯾﮏ ﺑﺎﺭ ﺩﺭ بازه‌ی ﭘﯿﺸﻨﻬﺎﺩﯼﺍﺵ ﺁﺭﺍﯾﺶ ﺷﻮﺩ. ﭼﻮﻥ ﻧﻤﯽﺩﺍﻧﯿﻢ ﺁﺭﺍﯾﺸﮕﺮ ﻗﺒﻞ ﺍﺯ ﺍﻭﻟﯿﻦ ﻣﺸﺘﺮﯼ ﻭ ﺑﻌﺪ ﺍﺯ ﺁﺧﺮﯾﻦ آن‌ها ﺑﻪ ﻣﺴﺎﻓﺮﺕ ﻣﯽﺭﻭﺩ ﯾﺎ ﻧﻪ، شما تعداد ﺑﺎﺯﻩﻫﺎﯼ ﮐﺎﺭﯼ ﺁﺭﺍﯾﺸﮕﺮ ﺭﺍ ﺩﺭ ﺧﺮﻭﺟﯽ ﺑﻨﻮﯾﺴﯿﺪ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ ﯾﮏ ﻣﺸﺘﺮﯼ ﻣﯽﺗﻮﺍﻧﺪ ﺩﺭ ﺭﻭﺯ ﺍﺑﺘﺪﺍﯼ بازه‌ی ﭘﯿﺸﻨﻬﺎﺩﯼﺍﺵ، ﺭﻭﺯ ﺍﻧﺘﻬﺎﯼ ﺁﻥ ﻭ ﯾﺎ ﺭﻭﺯﯼ ﺑﯿﻦ ﺁﻧﻬﺎ ﺁﺭﺍﯾﺶ ﺷﻮﺩ.
ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:
$n$ (تعداد مشتری‌ها) و ﺑﺎﺯﻩﺍﯼ ﮐﻪ ﻣﯽﺧﻮﺍﻫﻨﺪ، ﺩﻗﯿﻘﺎً ﯾﮏ ﺑﺎﺭ ﺩﺭ ﺁﻥ ﺁﺭﺍﯾﺶ ﮐﻨﻨﺪ ﺭﺍ ﺍﺯ ﻭﺭﻭﺩﯼ بخواند. کم‌ترین تعداد ﺑﺎﺯﻩﻫﺎﯼ ﮐﺎﺭﯼ ﺁﺭﺍﯾﺸﮕﺮ ﺭﺍ ﺑﯿﺎﺑﺪ ﻭ ﺩﺭ ﺧﺮﻭﺟﯽ ﭼﺎﭖ ﮐﻨﺪ. ﻭ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺍﯾﻦ ﻣﻘﺪﺍﺭ، ﺑﺮﺍﯼ ﻫﺮ ﻣﺸﺘﺮﯼ ﺗﻌﯿﯿﻦ ﻭﻗﺖ ﮐﻨﺪ.
ورودی
ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﻭﺭﻭﺩﯼ ﻋﺪﺩ $n$، تعداد مشتری‌ها آمده است.
در $n$ سطر بعد، در هر سطر به ترتیب روز ابتدا و روز انتهای بازه‌ی پیشنهادی یک مشتری آمده است. به مشتری‌ای که بازه‌ی پیشنهادش در سطر $i$ام آمده است مشتری $i$ام می‌گوییم.
هیچ بازه‌ی پیشنهادی برابر بازه‌ی دیگر نیست، هیچ بازه‌ی پیشنهادی شامل بازه‌ی دیگر نیست و $1\leq n \leq 2\times10^5$ است.
خروجی
در سطر اول خروجی کم‌ترین تعداد بازه‌های کاری را بنویسید.
در $n$ سطر باید روز آرایش هر مشتری چاپ شود. در سطر $i$ام باید روز آرایش مشتری $i$ام نوشته شود.
محدودیت‌ها
- محدودیت زمان: ۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
