ALAKE - Hồ nhân tạo
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
#define maxn 100003
#define oo 1000000001
long long n,w[maxn],h[maxn],t[maxn],s[maxn],kq[maxn],mini,tong=0;
int main()
{
//freopen("ALAKE.in","r",stdin);
scanf("%lld",&n);
h[0] = oo;
h[n+1] = oo;
mini = 1;
for(int i = 1;i<=n;i++)
{
scanf("%lld %lld",&w[i],&h[i]);
t[i] = i-1;
s[i] = i+1;
if(h[i]<h[mini])
mini = i;
}
while(h[mini]<oo)
{
kq[mini] = tong+w[mini];
s[t[mini]] = s[mini];
t[s[mini]] = t[mini];
if(h[t[mini]]<h[s[mini]])
{
tong = tong + w[mini]*(h[t[mini]]-h[mini]);
w[t[mini]] += w[mini];
mini = t[mini];
while(mini!= 0 && h[t[mini]]<h[mini])
mini = t[mini];
}
else
{
tong = tong + w[mini]*(h[s[mini]]-h[mini]);
w[s[mini]] += w[mini];
mini = s[mini];
while(mini!=n+1 && h[s[mini]]<h[mini])
mini = s[mini];
}
}
for(int i = 1;i<=n;i++)
printf("%lld\n",kq[i]);
//getch();
}