E. Бяцхан Артем ба Цаг хугацааны машин

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

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

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

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

Бяцхан Артем цаг хугацааны машин зохион бүтээжээ! Тэрээр ямар ч цаг хугацаанд очиж чадах болсон боловч түүний оюун санаа нь зөвхөн компьютерын шинжлэх ухаанаа бодсоор байв. Өөрөөр хэлбэл тэрээр уг машинаа нэгэн алдартай өгөгдлийн бүтэц болох Мулти-олонлог дээр ашиглахыг хүсжээ.

Артем бүхэл тоонуудын суурь мулти-олонлог зохион бүтээхийг хүсэж байгаа бөгөөд тэрээр уг өгөгдлийн бүтэц нь дараах 3 төрлийн үйлдлүүдийг дэмжин ажиллаж байхыг хүсэж байв:

  1. Мулти-олонлогт бүхэл тоо нэмэх. Олонлог болон мулти-олонлогийн ялгаа нь мулти-олонлог нэг бүхэл тоог хэд хэдэн удаа агуулсан байж болдог.
  2. Мулти-олонлогоос бүхэл тоог хасах. Гэвч уг үйлдлийг хийхэд хасагдаж буй бүхэл тооны зөвхөн нэг ширхэг нь хасагдах юм. Өөрөөр хэлбэл уг бүхэл тоо нь олон тооны удаа давтагдан орсон байвал уг үйлдлийг хийсний дараа уг бүхэл тоо нь мулти-олонлог дотор оршин байсаар байх юм. Артем ямар нэгэн зөрчил үүсгэхийг хүсэхгүй байгаа бөгөөд иймд тэрээр бүхэл тоог хасах үйлдэл хийгдэх болгонд уг хасагдаж буй бүхэл тоо нь мулти-олонлог дотор оршин байна гэж үзнэ.
  3. Өгөгдсөн бүхэл тоог уг мулти-олонлог дотор хэдэн удаа давтагдан орсон болохыг тоолох.

Гэхдээ цаг хугацааны машинаар яах билээ? Артем мулти-олонлогт эдгээр үйлдлүүдийг нэг нэгээр нь энгийн байдлаар гүйцэтгэхгүй ажээ. Одоо тэрээр хугацааны ялгаатай мөчүүдэд очин тухайн мөчдөө ямар нэгэн үйлдлийг гүйцэтгэх юм. Дараах жишээг авч үзье.

  • Эхлээд Артем хугацааны $1$-дэх мөчид мулти-олонлогт $5$ гэсэн бүхэл тоог нэмнэ.
  • Дараа нь хугацааны $5$-дахь мөчид мулти олонлогт $3$ гэсэн бүхэл тоог нэмнэ.
  • Дараа нь Артем хугацааны $6$-дахь мөчид очих ба мулти-олонлог дотор $5$ гэсэн бүхэл тоо хэдэн удаа давтагдан орсон болохыг асууна. Хариулт нь $1$ байна.
  • Дараа нь Артем цаг хугацаагаар буцаж аялах бөгөөд хугацааны $4$-дэх мөчид мулти-олонлог дотор $3$ гэсэн бүхэл тоо хэдэн удаа давтагдан орсон болохыг асууна. $3$ гэсэн бүхэл тоо нь зөвхөн хугацааны $5$-дахь мөчид мулти-олонлогт нэмэгдсэн учраас хугацааны $4$-дэх мөчид мулти-олонлог дотор $3$ гэсэн бүхэл тоо нь $0$ удаа давтагдсан байх юм.
  • Дараа нь Артем ахин цаг хугацаагаар буцаж аялах бөгөөд хугацааны $3$-дахь мөчид очин мулти-олонлогоос $5$ гэсэн бүхэл тоог хасна.
  • Эцэст нь Артем хугацааны $7$-дахь мөчид очин мулти-олонлог дотор $5$ гэсэн бүхэл тоог хэдэн удаа давтагдсан байгааг асуух юм. Бид хугацааны $3$-дахь мөчид $5$ гэсэн бүхэл тоог мулти-олонлогоос хассан учраас хариулт нь $0$ болно.

Артем зөрчил үүсэхэд үнэхээр дургүй бөгөөд тэрээр мулти-олонлогоос тоо хасах бүх үйлдлүүдийг хийхдээ зөвхөн мулти-олонлог дотор яг одоо оршин байгаа элементүүд дээр хийдэг байв. 3-дахь төрлийн үйлдлийн хариултыг тооцохдоо Артем уг үйлдлийг гүйцэтгэх хугацааны мөчид тооцохыг анхаарна уу. Иймд ирээдүйд түүний хийх үйлдлүүд нь уг үйлдлийн хариултад ямар нэгэн байдлаар нөлөөлөхгүй байх юм.

Артем-д уг цаг хугацаагаар аялагчийн мулти-олонлогийг хэрэгжүүлэхэд тусална уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) өгөгдөх ба энэ нь Артем-ын гүйцэтгэх үйлдлүүдийн тоог илэрхийлнэ.

Дараагийн $n$ мөрөнд үйлдлүүдийн тайлбар өгөгдөнө. Тайлбар болгон нь 3 ширхэг бүхэл тоо $a_{i}$, $t_{i}$ болон $x_{i}$ ($1 ≤ a_{i} ≤ 3$, $1 ≤ t_{i}, x_{i} ≤ 10^{9}$)-уудыг агуулах бөгөөд эдгээр нь харгалзан уг үйлдлийн төрөл, уг үйлдлийг гүйцэтгэхийн тулд Артемын аялж очих ёстой хугацааны мөч болон уг үйлдлийн утгыг тус тус илэрхийлнэ. Түүнчлэн бүх хугацааны мөчүүд нь ялгаатай байх бөгөөд үйлдэл бүрийг гүйцэтгэсний дараа эхний болон 2-дахь төрлийн бүх үйлдлүүд нь хоорондоо ямар нэгэн зөрчилгүй хэвээр байх юм.

Гаралт

3-р төрлийн үйлдэл болгоны хувьд өгөгдсөн хугацааны мөчид уг үйлдэл доторх бүхэл тоо нь мулти-олонлог дотор хэчнээн удаа давтагдсан болохыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5
Гаралт
1
2
1
Оролт
3
1 1 1
2 2 1
3 3 1
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...