Candies

Xem PDF



Tác giả:
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

\(n\) hộp kẹo, hộp thứ \(i\)\(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 2
Output
3
1

Bình luận


  • 0
    Phamvuphuong13 8:45 a.m. 12 Tháng 11, 2023

    cơ bản nhỉ <(")


    • 29
      PPAP_1264589 4:17 p.m. 5 Tháng 6, 2021

      Segment Tree với Lazy Update

      hoặc Fenwick Tree