C. Үйлдвэрийн засвар

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Үйлдвэр хуруувчийг их хэмжээгээр үйлдвэрлэдэг. Ерөнхийдөө өдөрт $a$ хүртэлх хуруувч үйлдвэрлэж чадна. Гэсэн хэдий ч зарим машин механизм ажиллахгүй үед үйлдвэр өдөрт $b$ хуруувч үйлдвэрлэж чадна. Үйлдвэр $k$ өдрийг арчилгаа байгуулалтын үе болгож сонгосон ба энэ үеэр үйлдвэр ямар ч хуруувч үйлдвэрлэхгүй боловч $k$ өдрийг дуусахаар бүрэн хүчин чадлаараа өдөрт $a$ хуруувч үйлдвэрлэнэ.

Эхэндээ ямар ч захиалга хүлээгдэхгүй байсан. Үйлдвэр дараах хэлбэртэй $d_{i}$, $a_{i}$ шинэчлэлүүдийг хүлээж авсан ба $d_{i}$-р өдөрт $a_{i}$ шинэ захиалга авсан. Захиалга бүр яг заагдсан өдөрт нэг хуруувч үйлдвэрлэсэн байхыг шаарддаг. Үйлдвэр нэг багцыг дүүргэх хэмжээний захиалгыг сонгоно.

Захиалгууд ирэхийн хэрээр үйлдвэрийн эзэн засвараа өгөгдсөн $p_{i}$ өдөрт эхлэх хүртлээ хамгийн ихдээ хэдэн захиалгыг биелүүлж чадахаа мэдэхийг хүсч байна. Эзэнд асуултынхаа хариуг олоход туслана уу.

Оролт

Эхний мөрөнд таван бүхэл тоон утга $n$, $k$, $a$, $b$, ба $q$ ($1 ≤ k ≤ n ≤ 200 000$, $1 ≤ b < a ≤ 10 000$, $1 ≤ q ≤ 200 000$) байх ба харгалзан өдрийн тоо, засварын хугацааны урт, үйлдвэрийн үйлдвэрлэх хүчин чадал, шинэчлэлийн тоо юм.

Дараагийн $q$ мөрөнд ажлуудын тайлбар байна. Ажлын тайлбар бүр доорх хоёр хэлбэрийн аль нэгээр бичигдэнэ:

  • $1d_{i} a_{i}$ ($1 ≤ d_{i} ≤ n$, $1 ≤ a_{i} ≤ 10 000$) нь $d_{i}$ өдөр дахь $a_{i}$ захиалгын шинэчлэл илэрхийлнэ эсвэл
  • $2p_{i}$ ($1 ≤ p_{i} ≤ n - k + 1$) нь хэрвээ үйлдвэр $p_{i}$ өдөр засварыг эхлүүлэхээр шийдсэн бол яг одоогийн байдлаар хэдэн захиалга гүйцэтгэж чадах вэ? гэсэн асуултыг илэрхийлнэ.

Оролтонд хамгийн багадаа нэг ширхэг хоёр дахь төрлийн ажил байна гэсэн үг.

Гаралт

Хоёр дахь төрлийн ажил бүрийн хувьд ганц бүхэл тоон утга агуулсан мөр хэвлэх ба уг тоо нь $n$ өдрийн туршид хамгийн ихдээ хэдэн захиалга гүйцэтгэж чадах тоог илэрхийлнэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 2 2 1 8
1 1 2
1 5 3
1 2 1
2 2
1 4 2
1 3 2
2 1
2 3
Гаралт
3
6
4
Оролт
5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2
Гаралт
7
1

Тэмдэглэл

Эхний жишээг авч үзье.

Бид өдөрт $1$ хүртэлх хуруувч үйлдвэрлэж байгаа ба засвар дууссаны дараа өдөрт $2$ хүртэлх хуруувч үйлдвэрлэнэ. Засвар $2$ өдөр хийгдэнэ.

Эхний ажлын хувьд бид $1$-р өдөр $1$ захиалга гүйцэтгэж чадна. $2$ болон $3$ дахь өдөр засвар хийгдэнэ. $4$ дахь өдөр нэг ч захиалга байхгүй учир нэг ч захиалга гүйцэтгэгдэхгүй, $5$ дахь өдөр $2$ захиалга хийгдэнэ учир нь бид үйлдвэрлэх чадамжаа багасгасан учир. Иймд нийт $3$ захиалга гүйцэтгэгдэнэ.

Гурав дахь ажлын хувьд $1$ дахь өдөр $1$ захиалга гүйцэтгэх боломжтой харин $2$ дахь өдөр $1$ захиалга харин $5$ дахь өдөр $2$ захиалга ингээд нийтдээ 4 захиалга болно.

Сэтгэгдлүүдийг ачааллаж байна...