KAGAIN - Chiến trường Ô qua

Tác giả: RR

Ngôn ngữ: Pascal

var
  a,left,right,stack:array[0..30111] of longint;
  tmp,i,n,test,top:longint;
  lr,lu,lv:longint;

begin
  read(test); a[0]:=0;
  for test:=1 to test do
    begin
      read(n);
      for i:=1 to n do read(a[i]);

      lr:=0;

      top:=0; stack[0]:=0;
      for i:=1 to n do
        begin
          while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
          left[i]:=stack[top]+1;
          inc(top); stack[top]:=i;
        end;

      top:=0; stack[0]:=n+1; a[n+1]:=a[0];
      for i:=n downto 1 do
        begin
          while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
          right[i]:=stack[top]-1;
          inc(top); stack[top]:=i;
        end;

      for i:=1 to n do
        begin
          tmp:=a[i]*(right[i]-left[i]+1);
          if (tmp>lr) or ((tmp=lr) and (left[i]<lu)) then
            begin
              lr:=tmp;
              lu:=left[i];
              lv:=right[i];
            end;
        end;

      writeln(lr,' ',lu,' ',lv);
    end;
end.

Download