Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Вилбур ба цэгүүд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Вилбур координатын хавтгай дээрх $n$ ширхэг цэгүүдийн олонлогоор тоглож байв.Бүх цэгүүд нь сөрөг биш бүхэл тоон координатуудтай.Түүнчлэн,хэрэв ямар нэгэн ($x$, $y$) цэг нь уг олонлогт харьяалагддаг бол $0 ≤ x' ≤ x$ болон $0 ≤ y' ≤ y$ ийм байх бүх ($x'$, $y'$) цэгүүд нь мөн уг олонлогт харьяалагдана.
Одоо Вилбур нь өөртөө байгаа олонлогийн цэгийн тоогоор тоглохыг хүссэн ба тэдгээрийг $1$-ээс $n$ хүртэлх ялгаатай бүхэл тоонуудад хуваарилах юм.Илүү гоо сайхны тааламжтай дугаарлах үүднээс,Вилбур хэрэв ямар нэгэн ($x$, $y$) цэг нь нь $i$ тоотой байвал $x' ≥ x$ болон $y' ≥ y$ байх олонлогийн бүх ($x'$,$y'$) цэгүүд нь $i$-аас багагүй тоонд хуваарилагдсан байна гэсэн нөхцөл заажээ.Жишээлбэл ($0$, $0$), ($0$, $1$), ($1$, $0$) болон ($1$, $1$) гэсэн 4-н цэгийн олонлогийн хувьд 2 янзын гоо сайхны тааламжтай дугаарлалт байна.Нэг нь $1$, $2$, $3$, $4$ ба нөгөө нэг нь $1$, $3$, $2$, $4$ юм.
Вилбур-ын найз цуг ирсэн ба Вилбур-тай өрсөлдөх юм.Ямар ч цэгийн хувьд тэрээр уг цэгийн онцгой утга $s(x, y) = y - x$-г тодорхойлно.Одоо тэрээр Вилбур-т $w_{1}$, $w_{2}$,..., $w_{n}$ өгөх ба түүнээс $i$ тоон дээр хуваарилагдах цэгийн онцгой утга нь $w_{i}$-тай тэнцүү буюу өөрөөр хэлбэл $s(x_{i}, y_{i}) = y_{i} - x_{i} = w_{i}$ байхаар олонлог дахь цэгүүдийг гоо сайхны тааламжтай дугаарлах хуваарилалтыг олохыг асуужээ.
Одоо Вилбур таныг уг өрсөлдөөнд туслахыг хүсжээ.
Оролт
Эхний мөрөнд Вилбур-ын тоглож байгаа олонлогийн цэгийг тоог илэрхийлэх ганц бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) өгөгдөнө.
Дараагийн $n$ ширхэг мөрөнд цэгүүдийн тайлбар байна.Мөр болгонд Вилбур-ын олонлогийн нэг цэгийг өгөх 2 бүхэл тоо $x$ болон $y$ ($0 ≤ x, y ≤ 100 000$) байна.Бүх цэгүүд нь ялгаатай байна.Мөн хэрэв ($x$, $y$) цэг нь оролтод өгөгдсөн бол $0 ≤ x' ≤ x$ болон $0 ≤ y' ≤ y$ байх бүх ($x'$, $y'$) цэгүүд нь мөн оролтод өгөгдөнө.
Оролтын сүүлийн мөрөнд $n$ ширхэг бүхэл тоо өгөгдөнө.Эдгээрийн $i$-дахь нь $w_{i}$ ($ - 100 000 ≤ w_{i} ≤ 100 000$) байх ба -- энэ нь ямар нэгэн гоо сайхны тааламжтай дугаарлалтын $i$ тоотой цэгийн шаардагдсан онцгой утгыг илэрхийлнэ.
Гаралт
Хэрэв олонлогийн цэгүүдийг $s(x_{i}, y_{i}) = y_{i} - x_{i} = w_{i}$ байхаар гоо сайхны тааламжтай дугаарлах хуваарилалт байвал гаралтын эхний мөрөнд "$YES$" гэж хэвлэнэ.Бусад тохиолдолд "$NO$" гэж хэвлэнэ.
Хэрэв бодолт байвал, $n$ ширхэг мөрөнд гаралтыг хэвлэнэ.$i$-дахь мөрөнд $i$ дугаартай цэгийг хэвлэнэ.Хэрэв олон хариулт байвал алийг нь ч хэвлэсэн болно.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
5 2 0 0 0 1 0 1 1 0 1 0 -1 -2 1 0
Гаралт
YES 0 0 1 0 2 0 0 1 1 1
Оролт
3 1 0 0 0 2 0 0 1 2
Гаралт
NO
Тэмдэглэл
Эхний жишээнд, ($2$, $0$) цэг $3$ дугаартай, ($0$, $0$) цэг $1$ дугаартай, ($1$, $0$) цэг $2$ дугаартай, ($1$, $1$) цэг $5$ дугаартай ба ($0$, $1$) цэг $4$ гэсэн дугаартай байх юм.Хэн ч уг дугаарлалт нь гоо сайхны тааламжтай ба $y_{i} - x_{i} = w_{i}$ байна гэдгийг хялбархан шалгаж чадна.
2-дахь жишээнд олонлогийн цэгүүдийн онцгой утгууд нь $0$, $ - 1$, болон $ - 2$ ба найзынх нь Вилбур-т өгсөн дараалал нь $0$, $1$, $2$ байна.Иймд хариулт байхгүй.