Codeforces Round #716 (Div. 2)
03:07:27 |
Codeforces Round #717 (Div. 2)
2 өдрийн дараа |
Codeforces Round #718 (Div. 1)
4 өдрийн дараа |
Codeforces Round #718 (Div. 2)
4 өдрийн дараа |
Codeforces Global Round 14
13 өдрийн дараа |
F. Баавгай ба Хими
хугацааны хязгаарлалт 6 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Лимак бол хими, урвал болон элементүүдийн хувирлыг сонирхон шохоорхдог ухаант хүрэн баавгай.
Лимакийн нутаг Бийрландад $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг элемент байдаг. Мөн элементүүдийг хувирган өөрчлөх чадалтай төхөөрөмж ч мөн бий. Төхөөрөмж бүр хоёр элементийг(өөр байх албагүй) илтгэх $a_{i}, b_{i}$ тоонуудаар тодорхойлогдоно. Өөрөөр хэлбэл энэ төхөөрөмжөөр $a_{i}$-г $b_{i}$ эсвэл $b_{i}$-г $a_{i}$ болгон өөрчлөх боломжтой. Бийрланд дах төхөөрөмжүүд тийм ч чанартай биш тул ихдээ нэг удаа л ашиглаж болохоор байдаг. $a_{i} = b_{i}$ байх боломжтой ба өөр төхөөрөмжүүд адил $a_{i}, b_{i}$ хосоор ч илэрхийлэгдэх боломжтой.
Рэйдвүүш нь Лимакийн хамгийн том дайсан бас өрсөлдөгч юм. Тэр Лимакийн химийн мэдлэгийг сорихыг хүсч байгаа аж. Тэд маргааш уулзах ба өөрсдийн бүх төхөөрөмжүүдээ авчирна. Лимакт $m$ төхөөрөмж бий, харин дайсандаа хэдий хэрийн юм байгааг түүнд гадарлах зүйл үгүй. Рэйдвүүш $x$ ба $y$ хоёр өөр элемент сонгоно. Лимак өөрийн болон Рэйдвүүшийн бүх төхөөрөмжийг хэрэглэх боломжтой. Тэр хэдэн ч төхөөрөмж ашиглаж болох ба тус бүрийг нь нэгээс олон удаа хэрэглэх боломжгүй. Лимак $x$ элементээс эхлэх ба эхлээд $y$ гаргаж авах ба буцаад түүнийг $x$ болгосон тохиолдолд даалгавар амжилттай гүйцэтгэгдсэн гэж үзнэ. Ингэвэл Рэйдвүүш Лимакийн химийн мэдлэгийг хүлээн зөвшөөрч зайгаа тавьж өгөх гэнэ.
Рэйдвүүшт өөрийн өөрийн дуртай хэсэг элементүүдийн хоосон бус олонлог байдаг ба тэр $x, y$ элементүүдээ энэ олонлогоос сонгоно. Олонлогт ямар элементүүд байдаг болон Рэйдвүүшт ямар төхөөрөмж байгаа талаар Лимак юу ч мэдэхгүй. Лимак тэр талаар $q$ ширхэг цуурхал (дараалал - queries) сонссон ба тэд тус бүрдээ Рэйдвүүшийн төхөөрөмж болоод дуртай элементүүдээс бүрдэнэ. Цуурхал бүрийн боломжит $x, y$ хосын хувьд даалгаврыг амжилттай гүйцэтгэж чадах эсэхээ Лимак мэдэхийг хүсч буй аж. Хэрэв тийм бол "YES" гэж хэвлэнэ үү. Харин Лимак гүйцэлдүүлж эс чадах $(x, y)$ хос өгөгдсөн олонлогоос олддог бол "NO" гэж хэвлэнэ.
Оролт
Эхний мөрөнд $n$, $m$, $q$ ($1 \le n, q \le 300 000, 0 \le m \le 300 000$) тоонууд өгөгдөнө, харгалзан элементүүдийн тоо, Лимакийн төхөөрөмжийн тоо, цуурхлын тоог илэрхийлнэ.
Дараагийн $m$ мөр тус бүр Лимакийн төхөөрөмжийг тодорхойлох $a_{i}$, $b_{i}$ ($1 \le a_{i}, b_{i} \le n$) тоонууд өгөгдөнө.
Цаашлаад $q$ цуурхлууд дараах байдлаар өгөгдөнө:
$i$-р цуурхлын эхний мөр $n_{i}$, $m_{i}$ ($1 \le n_{i} \le 300 000, 0 \le m_{i} \le 300 000$) хоёр тоо агуулна. Хоёр дах мөрөнд Рэйдвүүшийн дуртай элементүүдийг илтгэх $n_{i}$ ширхэг $x_{i, 1}, x_{i, 2}, ..., x_{i, n_{i}}$ ($1 \le x_{i, j} \le n$) ялгаатай бүхэл тоо өгөгдөнө. $n_{i} = 1$ байх боломжтойг тэмдэглэе, энэ тохиолдолд ялгаатай элементийн хослол үгүй тул хариулт үргэлж "YES" буюу Лимак шууд ялна. Дараагийн $m_{i}$ мөрүүд тус бүрдээ $i$-р цуурхал дах Рэйдвүүшийн төхөөрөмжийг тодорхойлох $a_{i, j}, b_{i, j}$ ($1 \le a_{i, j}, b_{i, j}$) хос тоо өгөгдөнө.
Бүх цуурхлуудын хувьд $n_{i}$-үүдийн нийлбэрийг авахад $300 000$-аас хэтрэхгүй. Мөн $m_{i}$-үүдийн нийлбэр ч $300 000$-аас үл халина.
Заавал унш: Цуурхлуудыг онлайнаар боловсруулах тул, Рэйдвүүшийн дуртай олонлог болон түүний төхөөрөмжүүд хувиргаж чадах элементүүдийг мэдэхийн тулд дараах функцийг ашиглана уу:
int rotate(int element)
{
element=(element+R)%n;
if (element==0) {
element=n;
}
return element;
}
Энд $R$ нь анхлан $0$ утгатай байх ба хариулт "YES" байх бүрд дарааллын (query) тоогоор өсөх юм. Дарааллууд (query) $1$-ээс эхлэн оролт дах эрэмбээрээ дугаарлагдсан болно.
Гаралт
$q$ ширхэг мөр хэвлэнэ. $i$-р цуурхлын $x$, $y$ хос бүрийн ($x_{i, 1}, x_{i, 2}, ..., x_{i, n_{i}}$ олонлог дотроос) хувьд Лимак амжилтанд хүрэх бол "YES", үгүй бол "NO" гэж хэвлэнэ үү.
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
6 5 4 1 2 2 3 3 4 2 4 5 6 2 0 4 2 2 1 6 2 3 4 3 2 6 3 4 2 5 4 6 2 1 1 2 1 2
Гаралт
YES NO YES YES
Оролт
7 6 2 1 2 1 3 2 4 2 5 3 6 3 7 7 2 1 2 3 4 5 6 7 4 5 6 7 7 2 1 2 3 4 5 6 7 4 6 5 7
Гаралт
NO YES
Тэмдэглэл
Эхний жишээ:
Эхний цуурхлын хувьд Рэйшвүүдийн дуртай олонлог ${4, 2}$ ба түүнд ямар ч төхөөрөмж байхгүй. Лимак $4$-г $2$-рүү хөрвүүлж чадах ба (даалгаврын эхний хагас нь гүйцэлдсэн гэсэн үг) цааш нь $2$-г $3$-руу, $3$-г $4$-рүү хувиргана. Хариу "YES", Иймд $R$ $1$-ээр өснө.
Хоёр дах цуурхлын хувьд олонлог нь ${6, 2}$ ба төхөөрөмж $(3, 4)$ юм, харин $R$ нэгтэй тэнцүү. Иймд олонлог ${1, 3}$ ба машин $(4, 5)$ гэсэн үг. Хариу "NO", Иймд $R$ өөрчлөгдөхгүй.
Гурав дах цуурхалд олонлог нь ${6, 4, 3}$ ба төхөөрөмжүүд $(2, 5)$ , $(4, 6)$ буюу ${1, 5, 4}$, $(3, 6)$ , $(5, 1)$ болно. ($R=1$ тул)
Рэйдвүүшийн сонголтуудыг авч үзвэл:
- Хэрвээ тэр $1$, $5$ элементүүдийг сонговол Лимак $1$-г $5$ руу, тэгээд $6$-г $3$ руу, $3$-г $2$ руу, $2$-г $1$ рүү хувиргаж чадна.
- Хэрвээ тэр $5$, $4$ элеметүүдийг сонговол, Лимак $5$-г $6$ руу, $6$-г $3$ руу, $3$-г $4$ (даалгаврын эхний хагас!), $4$-г $2$ руу, $2$-г $1$ рүү, $1$-г $5$ руу хөрвүүлж чадна.
- Хэрвээ $1$, $4$ элементүүдийг сонговол Лимак $1$-г $2$ руу, $2$-г $4$ рүү, $4$-г $3$ руу, $3$-г $6$ руу, $6$-г $5$ руу $5$-г $1$ рүү хувиргана.
Иймд Лимак даалгаврыг биелүүлж чадна. Хариулт "YES", мөн $R$ нь $3$-өөр өсч $4$ болно.
Сүүлийн цуурхал $ { 1, 2 } $, $(1, 2)$ нь $R$-н утгаас хамаарч ${ 5, 6 } $ , $(5, 6)$ болно. Одоо $2$ ширхэг $(5, 6)$ төрлийн төхөөрөмж байгаа тул Лимак мөн л даалгаврыг гүйцэтгэх боломжтой.