Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
A. Сэрэжа болон алгоритм
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сэрэжа бүх эрэмблэлтийн алгоритм-д дуртай. Тэр саяхан шинэ алгоритм бодож олсон ба энэ нь оролтондоо тэмдэгт мөр авдаг. Алгоритмын оролтын тэмдэгт мөрийг $q = q_1 q_2 ... q_k$ гэж үзье. Мөн алгоритм нь хоёр алхамаас бүрдэнэ.
q тэмдэгт мөрөөс дараалсан 3 үсгээс бүрдсэн дэд тэмдэгт мөр сонгож авах ба энэ нь "zyx", "xzy", "yxz" –ийн алинтай нь ч адилхан байх ёсгүй. Хэрэв тийм дэд тэмдэгт мөр олдохгүй бол алгоритм дуусна. Бусад тохиолдолд 2 дугаар алхам руу шилжинэ.
Сонгогдсон дэд тэмдэгт мөрийн үсэгнүүдээ дурын байрлалаар нь сольж 1 дүгээр алхам руу шилжинэ.
Сэрэжа хэрэв алгоритм зогсох боломж нь хоосон биш тохиолдолд q тэмдэгт мөр дээр зөв ажилна гэж бодож байгаа. Гэхдээ хэрвээ алгоритм нь ямартай ч тэмдэгт мөр дээр эцэс төгсгөлгүйгээр ажилвал бид тухайн тэмдэгт мөр дээр буруу ажилаж байна гэж үзнэ.
Сэрэжа алгоритмаа шалгахыг хүсч байгаа. Тиймээс түүнд n үсгээс бүтсэн $s = s_1 s_2 ... s_n$ тэмдэгт мөр байгаа. Хүү m ширхэг тесттэй цуваа дамжуулна. i дугаар тестэнд, тэр алгоритмийн оролт руу $s_{l_i} s_{l_i} + 1... s_{r_i}$ ($1 ≤ l_i ≤ r_i ≤ n$) дэд тэмдэгт мөр явуулна. Даанч түүний алгоритмын ажилгаа нь хэтэрхий урт тул Сэрэжа та бүхнээс тусламж хүсчээ. Тест бүрд ($l_i$, $r_i$) байх ба энэ явуулсан тестэнд зөв буруу ажилах эсэхийг тодорхойл.
Оролт
Эхний мөрөнд $10^5$ хэтрэхгүй бүхэл n урттай хоосон биш тэмдэгт мөр өгөгдсөн. Энэ тэмдэгт мөр нь ‘x’,’y’,’z’ -ээс бүтнэ.
Дараагийн мөрөнд m бүхэл тоо ($1 ≤ m ≤ 10^5$) – тестийн тоо. Дараагийн $m$ мөрөнд тестүүд агуулагдана. $i$ дугаар мөрөнд $l_i$, $r_i$ ($1 ≤ l_i ≤ r_i ≤ n$) 2 хос тоо агуулна.
Гаралт
Тест бүрд алгоритм зөв ажилаж байвал “YES” бусад тохиолдолд “NO” гэж хэвлэнэ.
Орчуулсан: Gantushig
Жишээ тэстүүд
Оролт
zyxxxxxxyyz 5 5 5 1 3 1 11 1 4 3 6
Гаралт
YES YES NO YES NO
Тэмдэглэл
In the first example, in test one and two the algorithm will always be terminated in one step. In the fourth test you can get string "xzyx$" on which the algorithm will terminate. In all other tests the algorithm doesn't work correctly.