Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
E. Тэрэгнүүд ба тэгш өнцөгтүүд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Поликарпуст $n × m$ хэмжээтэй шатрын хөлөг ба түүн дээр байрласан $k$ ширхэг тэрэг байлаа. Поликарпус эдгээрт тохирсон тоглоомын дүрэм зохиохоор шийдэв. Тэгээд аль хэдийн хөлөг дээр $q$ ширхэг стратегийн хувьд чухал гэж үзсэн тэгш өнцөгт талбайнуудыг тэмдэглэсэн байв. Тэр хэсгүүд аюулгүй байх ёстой. Поликарпусын хэлж байгаагаар стратегийн хувьд чухал тэгш өнцөгт нь түүн дээр байрлах тэрэгнүүд уг тэгш өнцөгтийн хоосон нүд бүрийг хамгаалж байвал аюулгүй байх болно. Харин уг тэгш өнцөгтөөс гадна байрлах тэрэг уг тэгш өнцөгтөд нөлөө үзүүлэхгүй. Тэрэгнүүдийн байрлал бэхлэгдсэн ба өөрчлөгдөхгүй. Сануулж хэлэхэд тэрэг нь өөрөөсөө хэвтээ болон босоо чиглэлд байрлах дараалсан хоосон нүднүүдийг хамгаалж байдаг. Поликарпуст бүх стратегийн тэгш өнцөгтүүд аюулгүй эсэхийг мэдэхэд туслаарай.
Оролт
Эхний мөрөнд хөлгийн хэмжээс, тэрэгний тоо болон стратегийн тэгш өнцөгтийн тоог илэрхийлэх $n$, $m$, $k$, $q$ ($1 ≤ n, m ≤ 100 000$, $1 ≤ k, q ≤ 200 000$) тоонууд байна. Хөлгийн нүднүүдийг хөндлөнгөөр $1$-ээс $n$ хүртэл, босоогоор $1$-ээс $m$ хүртэл дугаарлана. Дараагийн $k$ мөр бүрт "$x$ $y$" ($1 ≤ x ≤ n$, $1 ≤ y ≤ m$) гэсэн хос тоо байх ба тэрэгнүүдийн байрлалыг илэрхийлнэ. Тэрэг бүр ялгаатай нүдэнд байрлана. Дараагийн $q$ мөр бүрт стратегийн тэгш өнцөгтүүдийн байрлалыг илэрхийлэх "$x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$" ($1 ≤ x_{1} ≤ x_{2} ≤ n$, $1 ≤ y_{1} ≤ y_{2} ≤ m$) тоонууд өгөгдөнө. Харгалзах тэгш өнцөгт нь $x_{1} ≤ x ≤ x_{2}$, $y_{1} ≤ y ≤ y_{2}$ нөхцөлийг хангах бүх $(x, y)$ нүднээс тогтоно. Стратегийн тэгш өнцөгтүүд хоорондоо огтлолцож болно.
Гаралт
Хариуг $q$ мөрөнд хэвлэ. Стратегийн тэгш өнцөгт бүрийн хувьд аюулгүй бол "YES", бусад тохиолдолд "NO" гэж хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
4 3 3 3 1 1 3 2 2 3 2 3 2 3 2 1 3 3 1 2 2 3
Гаралт
YES YES NO
Тэмдэглэл
Жишээг зургаар дүрсэлбэл:
$(1, 2)$ нүд хамгаалагдаагүй тул сүүлийн тэгш өнцөгтийн хувьд "NO" гэж хэвлэнэ.