Tiệc Kẹo Gậy

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John có $N$ con bò với chiều cao ban đầu lần lượt là $h_{1}, h_{2}, \dots, h_{N}$ và $M$ cây kẹo gậy với chiều cao lần lượt là $c_{1}, c_{2}, \dots, c_{M}$ .

Nông dân John cho các con bò ăn kẹo gậy theo thứ tự từ cây kẹo thứ $1$ đến cây kẹo thứ $M$ . Với mỗi cây kẹo gậy, ban đầu cây kẹo được treo thẳng đứng chạm đất (phần dưới ở vị trí $0$ , phần trên ở vị trí bằng chiều cao cây kẹo). Các con bò lần lượt đến ăn theo thứ tự từ bò $1$ đến bò $N$ . Mỗi con bò ăn phần kẹo từ vị trí thấp nhất còn lại của cây kẹo cho đến chiều cao hiện tại của nó (nếu chiều cao con bò lớn hơn phần thấp nhất còn lại). Sau khi ăn, chiều cao của con bò tăng thêm đúng bằng lượng kẹo đã ăn.

Hãy tính chiều cao cuối cùng của mỗi con bò sau khi tất cả $M$ cây kẹo đã được cho ăn.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $M$ ( $1 \leq N, M \leq 2 \cdot 10^{5}$ ).
Dòng $2$ : $N$ số nguyên $h_{1}, h_{2}, \dots, h_{N}$ ( $1 \leq h_{i} \leq 10^{9}$ ) — chiều cao ban đầu của các con bò.
Dòng $3$ : $M$ số nguyên $c_{1}, c_{2}, \dots, c_{M}$ ( $1 \leq c_{i} \leq 10^{9}$ ) — chiều cao các cây kẹo gậy.

Dữ liệu ra

In ra $N$ dòng, dòng thứ $i$ là chiều cao cuối cùng của con bò thứ $i$ .

Ràng buộc

Các test $2$ - $10$ : $N, M \leq 10^{3}$ .
Các test $11$ - $14$ : Không có ràng buộc thêm.
Lưu ý: Cần sử dụng kiểu dữ liệu 64-bit.

Ví dụ

Input	Output	Giải thích
3 2 3 2 5 6 1	7 2 7	Cây kẹo đầu (cao 6): bò 1 ăn 3 đơn vị (cao 0->3), bò 2 không ăn được (cao 2 < phần thấp nhất 3), bò 3 ăn 2 đơn vị (cao 3->5). Chiều cao mới: [6, 2, 7]. Cây kẹo thứ 2 (cao 1): bò 1 ăn 1 đơn vị. Kết quả: [7, 2, 7].

Bình luận

Không có bình luận tại thời điểm này.