Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Музейн дээрэмчин
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Клеофасийн амьдардаг хотод нэгэн алдартай музей байдаг. Музейд удаан хугацаанд тавигдаж буй $n$ үзвэр ($1$-c $n$ хүртэл дугаарлагдсан) байх ба эдгээр үзвэрүүдийн $i$-р үзвэр нь $v_{i}$ утга болон $w_{i}$ масстай.
Ингээд музейг санхүүгийн том групп худалдаж авсан ба үзвэрүүдийг өөрчилж эхэлсэн. Энэ үед Клеофас музейг сонирхож эхэлсэн ба дараах зүйлсийг хэлж байна.
Та гурван төрлийн $q$ үйл явдлыг гүйцэтгэх ёстой:
- төрөл $1$ нь музей $v$ утга болон $w$ масстай үзвэр гарган тавина; энэ төрлийн $i$-р үйл явдалд гаргаж тавьсан үзвэр нь $n + i$ гэж дугаарлагдана (нарийн зүйлсийг жишээний тайлбараас харна уу)
- төрөл $2$ нь музей $x$ дугаартай үзвэрийг гаргах ба агуулахдаа аюулгүйгээр хадгална
- төрөл $3$ нь Клеофас музейд очих ба хэрвээ энд дээрэмчин байсан ба хулгайлсан үзвэрүүдийн нийт масс нь хамгийн ихдээ $m$ масстай байсан бол тэдгээрийн нийт утга нь хамгийн ихдээ хэд байж болох вэ? гэж бодно (мэдээж түүнд өөр чухал шалтгаан байхгүй).
3-р төрлийн үйл явдал бүрийн хувьд $s(m)$-г нийт масс нь $ ≤ m$ байх хулгайлагдсан үзвэрүүдийн боломжит хамгийн их утга гэе.
Илүү дэлгэрэнгүйгээр $D$-г одоо үзвэрт байгаа бүх үзвэрүүдийн дугааруудын бүрдэл гэе (анх $D$ = {1, ..., n} байна). $P(D)$ нь $D$-н бүх дэд бүрдлүүдийн бүрдэл байг мөн
байг.
Ингээд $s(m)$ нь
гэж тодорхойлогдоно.
бүрийн хувьд $s(m)$-г тооцоол. Гаралт нь тусгай форматтай байна.
Оролт
Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 5000$, $1 ≤ k ≤ 1000$) байх буюу музейн анхны үзвэрүүдийн тоо болон хулгайлагдсан үзвэрүүдийн хамгийн их масс байна.
Тэгээд $n$ мөр байна. Эдгээрийн $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр эерэг бүхэл тоо $v_{i}$ ба $w_{i}$ ($1 ≤ v_{i} ≤ 1 000 000$, $1 ≤ w_{i} ≤ 1000$) байх ба $i$-р үзвэрийн утга болон масс юм.
Дараагийн мөрөнд нэг бүхэл тоон утга $q$ ($1 ≤ q ≤ 30 000$) байх буюу үйл явдлуудын тоо юм.
Дараагийн $q$ мөр бүрт үйл явдлын тайлбар дараах форматтай байна:
- $1 v w$ нь 1 төрлийн үйл явдал бөгөөд $v$ утга $m$ масстай шинэ үзвэр нэмэгдсэн гэсэн үг ($1 ≤ v ≤ 1 000 000$, $1 ≤ w ≤ 1000$)
- $2 x$ нь 2 төрлийн үйл явдал бөгөөд $x$ дугаартай үзвэр хасагдсан гэсэн үг; хасагдсан үзвэр нь тухайн үед музейд тавигдсан үзвэр байна
- $3$ нь 3 төрлийн үйл явдал ба Клеофас музейд очих ба өөрийн асуултаа асууна
Энд хамгийн ихдээ $10 000$ ширхэг 1 төрлийн үйл явдал байх ба ядаж нэг ширхэг 3 төрлийн үйл явдал байна.
Гаралт
$s(m)$ утгын тоо нь их болж болох учир 3 төрлийн үйл явдлуудын хариултыг тусгай форматаар гарга.
3 төрлийн үйл явдал бүрийн хувьд $s(m)$-г уг үйл явдлын хувьд Клеофасийн асуултын хариулт гэж үзье; нэг мөрөнд нэг тоо -г хэвлэ. Энд $p = 10^{7} + 19$ ба $q = 10^{9} + 7$.
3 төрлийн үйл явдлуудын хариултуудыг оролтонд өгсөн дарааллаар хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 10 30 4 60 6 5 1 9 3 1 42 5 1 20 3 3 2 2 2 4 3 1 40 6 3
Гаралт
556674384 168191145 947033915 181541912
Оролт
3 1000 100 42 100 47 400 15 4 2 2 2 1 2 3 3
Гаралт
0
Тэмдэглэл
Эхний жишээн дээр 3 төрлийн үйл явдлуудын хувьд дэлгэгдсэн үзвэрүүдийн дугаар болон $s(1), ..., s(10)$ утгууд нь дараах дараалалтай байна:
Үзвэр тус бүрийн утгууд нь $v_{1} = 30, v_{2} = 60, v_{3} = 5, v_{4} = 42, v_{5} = 20, v_{6} = 40$ ба массууд нь $w_{1} = 4, w_{2} = 6, w_{3} = 1, w_{4} = 5, w_{5} = 3, w_{6} = 6$ байна.
Хоёр дахь жишээн дээр бүх үзвэр хасагдсаны дураа ганц асуулт асуугдсан ба дурын $m$-н хувьд $s(m) = 0$ байна.