Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ALAKE - Hồ nhân tạo

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<=1 000 000 000 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    |  1 |2|  3   | 

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         Sau 26 phút         Sau 50 phút 
Đoạn 1 bị phủ       Đoạn 3 bị phủ       Đ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


Được gửi lên bởi:sieunhan
Ngày:2008-12-30
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:USACO

hide comments
2016-09-24 15:39:03
Code đã AC:
http://shink.in/ndSTX
2013-10-17 17:02:31 a;slkfjasl;fkj
cũng khó đấy nhỉ :*

Last edit: 2013-10-19 12:06:04
2011-09-03 07:51:48 King siêu kul
cái hình ví dụ làm bằng ký tự mà đẹp nhỉ
2011-04-09 14:42:38 Ðỗ Việt Anh
đại loại N*W thuộc kiểu 64 bit
2011-04-09 14:41:45 Ðỗ Việt Anh
ai làm bài này chú ý cái W nó > 1000 đấy!
2010-12-26 09:57:20 Shiny Shiny Gold
Ùh
2010-10-28 17:06:36 Võ Quang Hòa
Sao mình đọc ví dụ mà không hiểu nhỉ :)
mấy cái W với H đó có ghi đúng không.
Mấy cái hoa thị * là thành bể và vách ngăn đúng không
2010-10-28 15:30:22 ðẹp trai ri bay


Last edit: 2010-10-28 15:34:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.