Hotel Queries
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(N\) khách sạn trên một con đường. Với mỗi khách sạn bạn biết được số phòng còn trống. Nhiệm vụ của bạn là chỉ định các phòng khách sạn cho \(M\) nhóm khách du lịch. Tất cả các thành viên trong cùng một nhóm muốn trọ chung một khách sạn.
Các nhóm sẽ lần lượt đến và bạn biết số phòng yêu cầu của mỗi nhóm. Với mỗi nhóm, bạn luôn tìm khách sạn đầu tiên mà đủ số phòng trống và chỉ định nhóm đấy vào phòng này. Sau đó, số phòng trống của khách sạn này sẽ giảm đi.
Input
- Dòng đầu tiên gồm hai số nguyên dương \(N,M\): Số khách sạn và số nhóm. Các khách sạn được đánh số theo thứ tự từ \(1\) tới \(N\).
- Dòng thứ hai gồm \(N\) số nguyên dương \(H_1,H_2,...,H_N\) \((1≤H_i≤10^9)\): số phòng trống của mỗi khách sạn.
- Dòng cuối cùng gồm \(M\) số nguyên dương \(R_1,R_2,...,R_M\) \((1≤Ri≤10^9)\): số phòng trống mà mỗi nhóm yêu cầu.
Output
- In ra \(M\) số nguyên là chỉ số của khách sạn được phân cho mỗi nhóm. Nếu nhóm nào đó không được chỉ định vào khách sạn (do không tìm được), in ra số \(0\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
- Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).
Example
Test 1
Input
8 5
3 2 4 1 5 5 2 6
4 4 7 1 1 Output
3 5 0 1 1
Bình luận
ideone.com/VXWwe8
À xin lỗi mọi người nha em đọc đề chưa kỹ ạ
Xin lỗi rất nhiều:))))))
Mình thấy đâu phúc tạp vậy đâu TKNP thôi
hint : seg_tree
kham khảo :))
ideone.com/VXWwe8