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.

Download