ALAKE - Hồ nhân tạo
Giới hạn- Thời gian: 0.09s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Những ngày hè nóng nực và ngột ngạt đã đến và những chú bò đang bắt đầu kêu ca. Bác John quyết định xây một hồ nước nhân tạo. Hồ nước có thể được mô tả như 1 vùng đất 2 chiều gồm N đoạn (N <= 100 000) đánh số từ 1 đến N từ trái sang phải. Đoạn thứ i được mô tả bởi 2 số nguyên W_i (1 <= W_i <= 1000) và H_i (1 <= H_i <= 10^9 lần lượt là độ rộng và chiều cao của đoạn thứ i. Không có 2 đoạn nào có độ cao bằng nhau. 2 bức tường cao vô tận chặn ở 2 đầu trái và phải. Sau đây là 1 ví dụ về hình dạng hồ nước.
* * :
* * :
* * 8
* *** * 7
* *** * 6
* *** * 5
* ********** 4 <- độ cao
* ********** 3
*************** 2
*************** 1
Đoạn |1111222333333|
Lúc mặt trời mọc, bác John bắt đầu đổ nước vào nơi có độ cao thấp nhất với tốc độ 1 ô vuông 1x1 trên 1 phút. Nước sẽ rơi xuống đến khi nó chạm vào đáy và chảy sang các vùng bên cạnh như thông thường
Nước Nước tràn
| |
* | * * | * * *
* V * * V * * *
* * * .... * *~~~~~~~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~**~~~~~~* *~~~~**~~~~~~*
* ********* *~~~~********* *~~~~*********
*~~~~********* *~~~~********* *~~~~*********
************** ************** **************
************** ************** **************
Sau 4 phút: Đoạn 1 bị phủ
Sau 26 phút: Đoạn 3 bị phủ
Sau 50 phút: Đoạn 2 bị phủ
Input
Dòng 1: N
Dòng 2..N+1: dòng thứ i+1 gồm 2 số W_i và H_i
Output
Gồm N dòng, dòng thứ i ghi thời điểm mà đoạn thứ i bị mực nước phủ lên với độ cao 1
Example
Input: 3 1 4 1 7 1 2 Output: 6 11 1
- Người up: huy391992
- Nguồn bài: USACO