ALAKE - Hồ nhân tạo
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 100111;
var
f1,f2 : text;
n,li : longint;
h,left,right,
stack,w,sumw : array[0..MAXN] of longint;
timel,neighl,neighr,sum,
timer,time : array[0..MAXN] of int64;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n); li:=1;
for i:=1 to n do
begin
read(f1,w[i],h[i]);
sum[i]:=sum[i-1]+int64(h[i])*w[i];
sumw[i]:=sumw[i-1]+w[i];
if h[i]<h[li] then
li:=i;
end;
end;
procedure init;
var
i,top:longint;
begin
h[0]:=1000111000; h[n+1]:=h[0];
top:=0; stack[top]:=0;
for i:=1 to n do
begin
while (top>0) and (h[stack[top]]<=h[i]) do dec(top);
left[i]:=stack[top];
inc(top); stack[top]:=i;
end;
top:=0; stack[top]:=n+1;
for i:=n downto 1 do
begin
while (top>0) and (h[stack[top]]<=h[i]) do dec(top);
right[i]:=stack[top];
inc(top); stack[top]:=i;
end;
for i:=1 to n do
begin
neighl[i]:=int64(h[i])*(sumw[i]-sumw[left[i]]) -(sum[i]-sum[left[i]]);
neighr[i]:=int64(h[i])*(sumw[right[i]-1]-sumw[i])-(sum[right[i]-1]-sum[i]);
end;
end;
procedure solve;
var
i,u:longint;
begin
time[li]:=w[li];
for i:=li+1 to n do
begin
u:=left[i];
timel[i]:=timel[u]+neighl[i];
time [i]:=timel[i]+neighr[i]+sumw[right[i]-1]-sumw[left[i]];
end;
for i:=li-1 downto 1 do
begin
u:=right[i];
timer[i]:=timer[u]+neighr[i];
time [i]:=timer[i]+neighl[i]+sumw[right[i]-1]-sumw[left[i]];
end;
for i:=1 to n do
writeln(f2,time[i]);
end;
begin
openF;
inp;
init;
solve;
closeF;
end.