Phòng Chống Lũ Quét
Xem PDFVì hằng năm đều có mùa lũ, quốc hội của đất nước Atlantis đã quyết định xây một công trình ngăn nước có dạng như sau.
Quốc hội sẽ chỉ đạo xây dựng \(N\) vách ngăn. Vách ngăn thứ \(i\) được xây tại vị trí \(P[i]\) và có độ cao \(H[i]\). Để kiểm tra độ hiểu quả của công trình, các đại biểu quyết định thực hiện \(M\) bài kiểm tra. Với mỗi bài kiểm tra, lượng nước \(Q\) sẽ được đổ vào vị trí \(0\). Kết quả được đánh giá bằng cách đếm số lượng bức vách ngăn mà dòng nước đã chảy qua trong bài thử đó.
Công việc xây dựng và việc chỉ đạo các bài kiểm thử đã sẵn sàng đi vào hoạt động. Tuy nhiên các đại biểu quốc hội cần phải chắc chắn rằng không được có một trận lũ nào sẽ đánh chìm quốc gia của họ như lịch sử rất lâu về trước, vì vậy mà họ triển khai rất nhiều đợi thử nghiệm. Bạn là một người kế toán của của dự án kiểm thử trên, hãy viết chương tính kết quả cùa \(M\) lần kiểm thử mà hội đồng yêu cầu.
Dữ liệu:
- Dòng đầu tiên chứa \(1\) số nguyên \(N\) \((1 \leq N \leq 2 * 10^5)\)
- Dòng thứ hai chứa \(N\) số nguyên \(P[i]\) \((1 \leq P[i] \leq 10^8)\), dữ liệu đảm bảo \(P[i]\) đôi một khác nhau
- Dòng thứ ba chứa \(N\) số nguyên \(H[i]\) \((1 \leq H[i] \leq 10^8)\)
- Dòng thứ tư chứa số nguyên \(M\) \((1 \leq M \leq 2*10^5)\)
- \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(Q\) \((1 \leq Q \leq 10^{16})\)
Kết quả:
- Gồm \(M\) dòng, mỗi dòng chứa duy nhất một số nguyên dương, với mỗi dòng là kết quả khi kiểm thử với lượng nước \(Q\) tương ứng
Test ví dụ
Input
3
2 6 4
2 1 3
3
4
5
20Output
0
1
3Note
Cấu trúc vách ngăn được xây có dạng như sau:
Khi lượng nước \(Q=4\) được chọn để đánh giá công trình, nước sẽ đọng lại ở phía bên trái của vách ngăn thứ nhất, không tràn được qua bức tường thứ 2, vì vậy mà kết quả bài thử này là \(0\)
Khi dùng lượng nước \(Q=5\), có \(1\) bức tường không thể ngăn được dòng nước chảy qua
Khi dùng lượng nước \(Q=20\), cả \(3\) bức tường đề không thể ngăn được dòng nước lũ
Bình luận
Bài này khó mà nhỉ, sao điểm ít vậy
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Ủa bài này dễ lắm hả =((
đr a azai