Codeforces Round #803 (Div. 2)
06:06:48 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
D. Улс дахь Замын түгжрэл
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нэг улс шулуун том замын дагуу байрласан $(n + 1)$ хотоос бүрддэг. Хотуудыг шулуун том замын дагуу тохиох дарааллаар нь $1$-c $n + 1$ хүртэлх дараалласан бүхэл тоонуудаар дугаарлацгаая. Иймээс хотууд том замын $n$ хэсгүүдээр холбогдсон ба $i$-р хэсэг нь $i$ болон $i + 1$ дугаартай хотуудыг холбоно. Том замын хэсэг бүр түүний замын бөглөрөлтэй байх үеийг илэрхийлэх эерэг бүхэл тоон утга $a_{i} > 1$-тай холбоотой.
$x$ хотоос $y$ ($x < y$) хот орохын тулд зарим жолооч нар дараах тактикуудыг ашиглана.
Анх жолооч $x$ хотод байх ба $t$ цаг тэгтэй тэнцүү байна. Жолооч $y$ хотод ирэх хүртлээ дараах үйлдлүүдийг гүйцэтгэнэ:
- хэрвээ одоогийн цаг $t$ нь $a_{x}$-н үржвэр болж байвал $x$ дугаартай том замын хэсэг нь одоо авто замын асуудалтай байгаа ба жолооч одоо байгаа хотдоо нэг хугацааны нэгж хугацаанд үлдэнэ (бид $t = t + 1$ болгоно).
- хэрвээ одоогийн цаг $t$ нь $a_{x}$-н үржвэр болохгүй байвал $x$ дугаартай том замын хэсэг нь одоо ямар ч түгжрэлгүй байгаа ба энэ нь жолооч $x + 1$ (бид $t = t + 1$ ба $x = x + 1$ болгоно) хотруу хугацааны нэг нэгжийг ашиглан очих шалтгаан юм.
Та шинэ авто замын удирдлагын систем хөгжүүлж байгаа. Та хоёр төрлийн дараалласан $q$ даалгаварыг гүйцэтгэнэ:
- $x$ хотоос $y$ ($x < y$) хот хүрэхэд $t$ цагийн эцсийн утгыг тодорхойлох ба бид дээр тодорхойлсон тактикуудыг хэрэгжүүлнэ гэж үз.
- $x$ дугаартай хэсэгт байгаа замын түгжрэлийн үеийг $y$ утгаар соль ($a_{x} = y$ болго).
Дээр өгөгдсөн даалгаваруудыг үр дүнтэйгээр биелүүлэх кодыг бич.
Оролт
Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{5}$) байх ба $n + 1$ хотуудыг холбох том замын хэсгүүдийн тоо.
Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($2 ≤ a_{i} ≤ 6$) байх ба том замын хэсгүүд дээрх замын түгжрэлийн үе.
Дараагийн мөрөнд нэг ширхэг бүхэл тоон утга $q$ ($1 ≤ q ≤ 10^{5}$) байх ба гүйцэтгэх даалгаваруудын тоо.
Дараагийн $q$ мөрөнд даалгаваруудын тайлбарууд $c$, $x$, $y$ ($c$ -- даалгаварын төрөл) форматтай байна.
Хэрвээ $c$ нь '$A$' тэмдэгт байвал таны ажил эхний төрлийн даалгаварыг гүйцэтгэх байна. Энэ тохиолдолд дараах хязгаарлалтууд байна: $1 ≤ x < y ≤ n + 1$.
Хэрвээ $c$ нь '$C$' тэмдэгт байвал таны ажил хоёрдугаар төрлийн даалгаварыг гүйцэтгэх байна. Энэ тохиолдолд дараах хязгаарлалтууд байна: $1 ≤ x ≤ n$, $2 ≤ y ≤ 6$..
Гаралт
Эхний төрлийн даалгавар бүрийн хувьд $x$ хотоос $y$ хотод очиход $t$ цагийн эцсийн утгыг илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ. Даалгаваруудыг оролтонд өгөгдсөн дарааллаар гүйцэтгэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
10 2 5 3 2 3 5 3 4 2 4 10 C 10 6 A 2 6 A 1 3 C 3 4 A 3 11 A 4 9 A 5 6 C 7 3 A 8 10 A 2 5
Гаралт
5 3 14 6 2 4 4