Candies
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Có \(n\) hộp kẹo, hộp thứ \(i\) có \(a_i\) viên và tất cả \(m\) người lần lượt tới ăn. Người thứ \(i\) sẽ chỉ ăn kẹo ở các hộp có số lượng còn lại không ít hơn \(t_i\) chiếc và sẽ ăn ở những hộp này, mỗi hộp một viên.
Yêu cầu: Hãy xác định số kẹo từng người đã ăn.
Input
- Dòng đầu tiên chứa số nguyên dương \(n\) (\(n\le 10^5\)),
- Dòng thứ 2 chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n\) (\(a_i\le 10^9\))
- Dòng thứ 3 chứa số nguyên dương \(m\) (\(m\le 10^5\)),
- Dòng thứ 4 chứa \(m\) số nguyên dương \(t_1,t_2,…,t_M\) (\(t_i\le 10^9\)),
Output
- Đưa ra m số nguyên, mỗi số trên một dòng. Số thứ \(i\) là số viên kẹo người thứ \(i\) đã ăn.
Example
Test 1
Input
3
3 1 1
2
1 2Output
3
1
Bình luận
Mình xin gợi ý code bài này với ạ
cơ bản nhỉ <(")
Segment Tree với Lazy Update
hoặc Fenwick Tree