المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۱۷

Stylist

آرایشگر تنبل قصه‌ی ما، ﻫﺮ ﺭﻭﺯ ﺣﺪﺍﮐﺜﺮ ﯾﮏ ﻣﺸﺘﺮﯼ ﺭﺍ ﺁﺭﺍﯾﺶ ﻣﯽﮐﻨﺪ. ﺍﻭ ﻫﺮ ﺭﻭﺯﯼ ﮐﻪ ﺑﯿﮑﺎﺭ ﻣ‰ﯽﺷ‰ﻮﺩ، ﺑ‰ﻪ ﻣ‰ﺴ‰ﺎﻓ‰ﺮﺕ ﻣ‰ﯽﺭﻭﺩ ﻭ ﺗ‰ﺎ ﻭﻗ‰ﺘ‰ﯽ ﻣ‰ﺸ‰ﺘ‰ﺮﯼ ﺩﯾ‰ﮕ‰ﺮﯼ ﻧ‰ﺒ‰ﺎﺷ‰ﺪ، ﺑ‰ﺎﺯ ﻧ‰ﻤ‰ﯽﮔ‰ﺮﺩﺩ. ﺷ‰ﻮﻫ‰ﺮ ﺍﻭ ﺍﺯ ﺍﯾ‰ﻦ ﻣﻮﺿﻮﻉ ﺑﺴﯿﺎﺭ ﻧﺎﺭﺍﺣﺖ ﺍﺳﺖ ﻭ ﻣﯽﺧﻮﺍﻫﺪ ﻃﻮﺭﯼ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﮐﻨﺪ ﮐﻪ ﺯﻧﺶ ﮐﻢ ﺑﻪ ﻣﺴﺎﻓﺮﺕ ﺑﺮﻭﺩ. ﺍﻭ ﺍﺯ ﺗﻤﺎﻣﯽ ﻣﺸﺘﺮﯾﻬﺎﯼ ﻫﻤﺴﺮ، بازه‌ی ﺯﻣﺎﻧﯽﺍﯼ ﮐﻪ ﻣﯽﺧﻮﺍﻫﻨﺪ ﺩﺭ ﺁﻥ ﺑﻪ ﺁﺭﺍﯾﺸﮕﺎﻩ ﺑﺮﻭﻧﺪ، ﺭﺍ ﮔﺮﻓﺘﻪ ﻭ ﺣﺎﻻ ﺑﻪ ﺩﻧﺒﺎﻝ ﺗﻌﯿﯿﻦ روز ﺯ ﺁﺭﺍﯾﺶ ﻫﺮ ﻣﺸﺘﺮﯼ ﺍﺳﺖ ﻃﻮﺭﯼ ﮐﻪ ﺗﻌﺪﺍﺩ ﻣﺴﺎﻓﺮﺗﻬﺎﯼ ﺁﺭﺍﯾﺸﮕﺮ، کم‌ترین ﻣ‰ﻘ‰ﺪﺍﺭ ﻣ‰ﻤ‰ﮑ‰ﻦ ﺷ‰ﻮﺩ. ﺷ‰ﻮﻫ‰ﺮ ﺁﺭﺍﯾ‰ﺸ‰ﮕ‰ﺮ ﻭﻗ‰ﺘ‰ﯽ ﺑ‰ﺎﺯﻩﻫ‰ﺎﯼ ﺗ‰ﻤ‰ﺎﻡ ﻣ‰ﺸ‰ﺘ‰ﺮﯼﻫ‰ﺎ ﺭﺍ ﭘ‰ﺮﺳ‰ﯿ‰ﺪ، ﻣ‰ﺘ‰ﻮﺟ‰ﻪ ﺷ‰ﺪ ﮐ‰ﻪ ﻫ‰ﯿ‰ﭻ ﺑ‰ﺎﺯﻩﺍﯼ ﺑ‰ﺮﺍﺑ‰ﺮ ﺑ‰ﺎ ﺩﯾ‰ﮕ‰ﺮﯼ ﻭ ﯾ‰ﺎ ﺷ‰ﺎﻣ‰ﻞ ﺁﻥ ﻧ‰ﯿ‰ﺴ‰ﺖ. ﺍﻭ ﺍﺯ ﻫ‰ﻤ‰ﯿ‰ﻦ ﻣ‰ﻮﺿ‰ﻮﻉ ﻣ‰ﺘ‰ﻮﺟ‰ﻪ ﺷ‰ﺪ ﮐ‰ﻪ ﻣ‰ﯽﺗ‰ﻮﺍﻥ ﻃ‰ﻮﺭﯼ ﺗﻤﺎﻣﯽ ﻣﺸﺘﺮﯼﻫﺎ ﺭﺍ ﺗﻌﯿﯿﻦ ﻭﻗﺖ ﮐﺮﺩ ﮐﻪ ﻫﻤﺴﺮﺵ همه‌ی آن‌ها ﺭﺍ ﺁﺭﺍﯾﺶ ﮐﻨﺪ ﻭ ﻣﺠﺒﻮﺭ ﻧﺸﻮﺩ ﺩﺭ ﯾﮏ ﺭﻭﺯ ﺩﻭ ﻣﺸﺘﺮﯼ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ.

ﺷﻤﺎ ﺑﺎﯾﺪ ﺑﺮ ﺍﺳﺎﺱ ﺑﺎﺯﻩﺍﯼ ﮐﻪ ﻫﺮ ﻣﺸﺘﺮﯼ ﻣﯽﺧﻮﺍﻫﺪ ﺩﺭ ﺁﻥ ﺁﺭﺍﯾﺶ ﺷﻮﺩ، ﺍﯾﻦ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﺭﺍ ﺑﺮﺍﯼ شوهر بیچاره‌ی آرایشگر ﺍﻧ‰ﺠ‰ﺎﻡ ﺩﻫ‰ﯿ‰ﺪ. ﻫ‰ﺮ ﻣ‰ﺸ‰ﺘ‰ﺮﯼ ﺑ‰ﺎﯾ‰ﺪ ﺩﻗ‰ﯿ‰ﻘ‰ﺎً ﯾ‰ﮏ ﺑ‰ﺎﺭ ﺩﺭ بازه‌ی ﭘ‰ﯿ‰ﺸ‰ﻨ‰ﻬ‰ﺎﺩﯼﺍﺵ ﺁﺭﺍﯾ‰ﺶ ﺷﻮﺩ. ﭼﻮﻥ ﻧﻤﯽﺩﺍﻧﯿﻢ ﺁﺭﺍﯾﺸﮕﺮ ﻗﺒﻞ ﺍﺯ ﺍﻭﻟﯿﻦ ﻣﺸﺘﺮﯼ ﻭ ﺑﻌﺪ ﺍﺯ ﺁﺧﺮﯾﻦ آن‌ها ﺑﻪ ﻣﺴﺎﻓﺮﺕ ﻣﯽﺭﻭﺩ ﯾﺎ ﻧﻪ، شما تعداد ﺑﺎﺯﻩﻫﺎﯼ ﮐﺎﺭﯼ ﺁﺭﺍﯾﺸﮕﺮ ﺭﺍ ﺩﺭ ﺧﺮﻭﺟﯽ ﺑﻨﻮﯾﺴﯿﺪ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ ﯾﮏ ﻣﺸﺘﺮﯼ ﻣﯽﺗﻮﺍﻧﺪ ﺩﺭ ﺭﻭﺯ ﺍﺑﺘﺪﺍﯼ بازه‌ی ﭘﯿﺸﻨﻬﺎﺩﯼﺍﺵ، ﺭﻭﺯ ﺍﻧﺘﻬﺎﯼ ﺁﻥ ﻭ ﯾﺎ ﺭﻭﺯﯼ ﺑﯿﻦ ﺁﻧﻬﺎ ﺁﺭﺍﯾﺶ ﺷﻮﺩ.

ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:

$n$ (تعداد مشتری‌ها) و ﺑﺎﺯﻩﺍﯼ ﮐﻪ ﻣﯽﺧﻮﺍﻫﻨﺪ، ﺩﻗﯿﻘﺎً ﯾﮏ ﺑﺎﺭ ﺩﺭ ﺁﻥ ﺁﺭﺍﯾﺶ ﮐﻨﻨﺪ ﺭﺍ ﺍﺯ ﻭﺭﻭﺩﯼ بخواند. کم‌ترین تعداد ﺑﺎﺯﻩﻫﺎﯼ ﮐﺎﺭﯼ ﺁﺭﺍﯾﺸﮕﺮ ﺭﺍ ﺑﯿﺎﺑﺪ ﻭ ﺩﺭ ﺧﺮﻭﺟﯽ ﭼﺎﭖ ﮐﻨﺪ. ﻭ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺍﯾﻦ ﻣﻘﺪﺍﺭ، ﺑﺮﺍﯼ ﻫﺮ ﻣﺸﺘﺮﯼ ﺗﻌﯿﯿﻦ ﻭﻗﺖ ﮐﻨﺪ.

ورودی

ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﻭﺭﻭﺩﯼ ﻋﺪﺩ $n$، تعداد مشتری‌ها آمده است.

در $n$ سطر بعد، در هر سطر به ترتیب روز ابتدا و روز انتهای بازه‌ی پیشنهادی یک مشتری آمده است. به مشتری‌ای که بازه‌ی پیشنهادش در سطر $i$ام آمده است مشتری $i$ام می‌گوییم.

هیچ بازه‌ی پیشنهادی برابر بازه‌ی دیگر نیست، هیچ بازه‌ی پیشنهادی شامل بازه‌ی دیگر نیست و $1\leq n \leq 2\times10^5$ است.

خروجی

در سطر اول خروجی کم‌ترین تعداد بازه‌های کاری را بنویسید.

در $n$ سطر باید روز آرایش هر مشتری چاپ شود. در سطر $i$ام باید روز آرایش مشتری $i$ام نوشته شود.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4
6 6
1 3
2 5
7 10
2
6
1
2
7

ابزار صفحه