Codeforces Round #804 (Div. 2)
23:18:36 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
C. Тайлан
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сар бүр Блэйк "Блэйк Технологи" компанийн эдийн засгийн үндсэн үзүүлэлтүүдийг агуулсан тайлан хүлээн авдаг. Энд компаний гаргасан $n$ ширхэг бүтээгдэхүүн байна. Эдгээрийн нэг бүрийн хувьд эцсийн тайлан болох ганц бүхэл тоон утга байх ба харгалзах орлогыг илтгэнэ. Тайлан Блэйк-д ирэхээс өмнө $m$ менежерүүдийн гараар дамжсан. Тэдгээрийн нэг бүр элементүүдийг өөр дараалалтай болгож өөрчилсан байж магадгүй. Өөрөөр хэлбэл $i$-р менежер эхний $r_{i}$ тоог буурсан биш эсвэл өссөн биш дарааллаар дарааллуулаад тайланг $i+1$ менежерт эсвэл шууд Блэйкруу(хэрвээ менежерийн дугаар $i = m$ байвал) дамжуулна.
"Блэйк Технологи" компанийн ажилчид яг одоо тайлангаа бэлдэж байна. Та анхны дараалал болох $n$ урттай $a_{i}$-г мэдэх ба менежер бүрийн тайлбар болох $r_{i}$ утгыг мэдэх ба энэ нь түүний дуртай дараалал юм. Та үйл явцыг хурдасгаж эцсийн тайлангийн харагдах байдлыг тодорхойлох хэрэгтэй.
Оролт
Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 200 000$) байх ба харгалзан тайланд байгаа бүтээгдэхүүний тоо ба менежерүүдийн тоо юм.
Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{i}$ ($|a_{i}| ≤ 10^{9}$) байх ба менежерүүдэд очихоос өмнөх анхны тайлан.
Дараагийн $m$ мөрөнд менежерүүдийн хийх гэж буй үйлдлүүдийн тодорхойлолтууд байна. $i$-р мөр бүрт хоёр бүхэл тоон утга $t_{i}$ ба $r_{i}$ (, $1 ≤ r_{i} ≤ n$) байх ба $i$-р менежер эхний $r_{i}$ тоог буурсан биш(хэрвээ $t_{i} = 1$ байвал) эсвэл өссөн биш (хэрвээ $t_{i} = 2$ байвал) дарааллаар альнаар нь эрэмбэлэхийг заана.
Гаралт
Гаралтанд $n$ ширхэг бүхэл тоон утга буюу $m$ менежерээр дамжин Блэйкд очих тайлан юм.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 1 1 2 3 2 2
Гаралт
2 1 3
Оролт
4 2 1 2 4 3 2 3 1 2
Гаралт
2 4 1 3
Тэмдэглэл
Эхний жишээн дээр анхны тайлан: $1 2 3$ гэж харагдана. Эхний менежерийн дараа эхний хоёр тоо байраа сольсон байна: $2 1 3$. Блэйкд тайлан энэ хэлбэрээрээ ирнэ.
Хоёр дахь жишээн дээр анхны тайлан: $1 2 4 3$ хэлбэртэй байна. Эхний менежер тайланг $4 2 1 3$ болгож өөрчилнө. Хоёр дахь менежерийн өөрчлөлтийн дараа тайлан $2 4 1 3$ болно. Энэ тайлан Бдэйкт хүргэгдэнэ.