المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

ورودی

  • سطر اول ورودی شامل سه عدد طبیعی، $1 \leq N \leq 10^5$، تعداد روزها، و $1 \leq M \leq N$، تعداد ورزش‌های المپیک و $1 \leq Q \leq l0^5$، تعداد پرسش‌ها، است.
  • سطر دوم شامل $N$ عدد طبیعی $ 1 \leq A_1, \cdots, A_N \leq M$ به طوری که $A_i$ ورزش انجام شده در روز $i$-ام است.
  • سطرهای سوم تا $Q+2$-ام ورودی هر کدام شامل دو عدد طبیعی $1 \leq L \leq R \leq N$ هستند که سطر $i+2$-ام ورودی، بازه‌ی مورد پرسش در سوال $i$-ام را نشان می‌دهد
  • تضمین می‌شود به ازای هر $1 \leq i \leq M$ عدد $j$ی وجود دارد کهA_j= i باشد.
  • در ۲۰ درصد از ورودی‌ها، $1 \leq N \leq 1000$ و $1 \leq Q \leq 1000$، است.
  • در ۵۰ درصد از ورودی‌ها، $1 \leq M \leq 100$، است.

خروجی

خروجی شامل $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

ابزار صفحه