Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:عملی نهایی دوم:سوال ۳

برنامه‌ریزی المپیک

مسابقات المپیک در پیشرو است و برگزارکنندگان قصد دارند این مسابقات را در N روز برگزار کنند به طوریکه در هر روز تنها یک ورزش انجام شود. می‌دانیم المپیک شامل M ورزش متفاوت است که برای سادگی کار آن‌ها را با 1 تا M شماره‌گذاری کرده‌اند. حال برگزار کنندگان مسابقه برنامه‌ی پیشنهادی خود را برای برگزاری بازی‌های این مسابقات، به صورت یک آرایه 1A1,,ANM به آقا داوود داده‌اند که به عنوان یک پیشکسوت در عرصه‌ی ورزش، نظر خود را نسبت به آن اعلام کند. از نظر آقا داوود بازه‌ی [L,R] از روزها کسل‌کننده است، اگر هیچ روزی در بین روزهای L-ام تا R-ام، (شامل خود این دو روز) وجود نداشته باشد، که ورزش انجام شده در آن روز، دقیقا یک بار در بین روزهای L تا R انجام شده باشد. حال از نظر آقا داوود بازه‌ی [L,R] کسل‌کنندهی بالقوه است، اگر و فقط اگر S و Eای داشته باشیم که SLRE و بازهی [S,E] کسل‌کننده باشد. حال از شما تعداد زیادی پرسش درباره‌ی بازه‌های متفاوتی پرسیده می‌شود و شما باید برای هرکدام از این بازه‌ها تشخیص دهید کسل‌کننده‌ی بالقوه هستند یا نه.

ورودی

  • سطر اول ورودی شامل سه عدد طبیعی، 1N105، تعداد روزها، و 1MN، تعداد ورزش‌های المپیک و 1Ql05، تعداد پرسش‌ها، است.
  • سطر دوم شامل N عدد طبیعی 1A1,,ANM به طوری که Ai ورزش انجام شده در روز i-ام است.
  • سطرهای سوم تا Q+2-ام ورودی هر کدام شامل دو عدد طبیعی 1LRN هستند که سطر i+2-ام ورودی، بازه‌ی مورد پرسش در سوال i-ام را نشان می‌دهد
  • تضمین می‌شود به ازای هر 1iM عدد jی وجود دارد کهA_j= i باشد.
  • در ۲۰ درصد از ورودی‌ها، 1N1000 و 1Q1000، است.
  • در ۵۰ درصد از ورودی‌ها، 1M100، است.

خروجی

خروجی شامل Q سطر است که در سطر i-ام آن، پاسخ به پرسش i-ام آمده است. در صورتی که بازه‌ی پرسش i-ام کسل‌کننده‌ی بالقوه باشد، عبارت YES و در غیر این صورت عبارت NO را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 2 2
1 2 1 2
1 1
1 4
YES
Yes
5 3 3
1 1 3 2 2
1 4
4 5
1 5
No
YES
NO

ابزار صفحه