Hồ nhân tạo

3607. Hồ nhân tạo

Mã bài: ALAKE

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

Link:

Solution:
DevC:

#include<stdio.h>

// #include<conio.h>

#define MaxN 100005
const long int INF=1000000005;

long long int result[MaxN],total=0;
long int N;
long int W[MaxN];
long int H[MaxN];
long int Next[MaxN],Prev[MaxN];

int main()
{
    long int i;
 
    scanf("%ld",&N);
    i=1;
    long int pos=1;
    while(i<=N)
    {
     scanf("%d%ld",&W[i],&H[i]);
     if(H[i]<H[pos]) pos=i;
     Next[i]=i+1;
     Prev[i]=i-1;
     i++;        
    }
 
    H[0]=INF;
    H[N+1]=INF;
 
    while(H[pos]<INF)
    {
     result[pos]=total+W[pos];
     Next[Prev[pos]]=Next[pos];
     Prev[Next[pos]]=Prev[pos];
     if(H[Prev[pos]]<H[Next[pos]])
     {
      total+=(long long int )(W[pos])*(H[Prev[pos]]-H[pos]);              
      W[Prev[pos]]+=W[pos];
      pos=Prev[pos];
      while(pos>0&&H[Prev[pos]]<H[pos]) pos=Prev[pos];
     }
     else
     {
      total+=(long long int )(W[pos])*(H[Next[pos]]-H[pos]);
      W[Next[pos]]+=W[pos];
      pos=Next[pos];
      while(pos<=N&&H[Next[pos]]<H[pos]) pos=Next[pos];
     }              
    }
 
    i=1;
    while(i<=N)
    {
     printf("%lld\n",result[i]);
     i++;        
    }
 //   printf("%lld",result[i]);
 
//    getch();
    return 0;
}