Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
B. Евгений болон дууны жагсаалт
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Евгенийгийн дууны жагсаалтанд $n$ ширхэг дуу байдаг. $i$ дэхь дуу $t_{i}$ минут урттай. Евгений дуу болгоныг нэг эсвэл нэгээс олон удаа сонсоно. Тэрээр $i$ дэхь дууг $c_{i}$ удаа сонсоно. Евгенийгийн дууны жагсаалт дараах байдлаар дуунуудыг түүнд сонсгоно: $1$ дэхь дууг $c_{1}$ удаа, тэгээд $2$ дахь дууг $c_{2}$ удаа гэх мэт сонсгон хамгийн сүүлд $n$ дэхь дууг $c_{n}$ удаа сонсгоно.
Евгений цаас аван $m$ ширхэг минут буюу дуу таалагдсан минутуудыг тэмдэглэж авчээ. Одоо тэрээр тухайн таалагдсан мөчүүдэд хэд дэхь дуу явж байсныг мэдэхийг хүсчээ. Евгенийд туслан эдгээр дууны дугаарыг олно уу.
Оролт
Эхний мөрөнд $n$, $m$ $(1 ≤ n, m ≤ 10^{5})$ бүхэл тоо өгөгдөнө.
Дараагийн $n$ мөрийн $i$ дэхь мөрөнд дууны жагсаалтын тодорхойлолт болох $2$ ширхэг бүхэл тоо $c_{i}, t_{i}$ $(1 ≤ c_{i}, t_{i} ≤ 10^{9})$ өгөгдөнө. Дууны жагсаалтын нийт тоглогдох хугацаа $10^{9}$-ыг хэтрэхгүй $(\sum\limits_{i=1}^{n} c_i \cdot t_i \leq 10^9)$.
Дараагийн мөрөнд $m$ ширхэг эерэг бүхэл тоонууд $v_{1}, v_{2}, ..., v_{m}$ өгөгдөнө. Эдгээр нь Евгенийгийн тэмдэглэж авсан минутууд. Эдгээр минутууд дуу явж байхад тэмдэглэсэн байх буюу $v_{i} < v_{i + 1}$ $(i < m)$ нөхцлийг хангах нь баталгаатай ($v_i$ - Евгенийгийн тэмдэглэж авсан минут).
Гаралт
$m$ ширхэг бүхэл тоо хэвлэнэ үү. $i$ дэхь тоо нь Евгений дууны жагсаалтыг тоглуулж эхлэсэнээс хойш $v_{i}$ дэхь минутанд тоглогдож байсан дууны дугаар юм.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
1 2 2 8 1 16
Гаралт
1 1
Оролт
4 9 1 2 2 1 1 1 2 2 1 2 3 4 5 6 7 8 9
Гаралт
1 1 2 2 3 4 4 4 4