結果

問題 No.3238 Shadow
ユーザー tomerun
提出日時 2025-08-15 22:21:17
言語 Crystal
(1.14.0)
結果
AC  
実行時間 362 ms / 2,000 ms
コード長 1,751 bytes
コンパイル時間 10,813 ms
コンパイル使用メモリ 309,704 KB
実行使用メモリ 18,044 KB
最終ジャッジ日時 2025-08-15 22:21:40
合計ジャッジ時間 14,072 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = read_line.to_i
p = read_line.split.map(&.to_i)
rev = Array.new(n + 1, 0)
n.times { |i| rev[p[i]] = i }
st = SegTree(Int32).new(p, ->(a : Int32, b : Int32) { {a, b}.min }, n + 1)
while true
  right = n
  min_x = n
  min_y = n
  while right > 0
    min = st.get(0, right)
    break if min == n + 1
    min_x = {min_x, rev[min]}.min
    min_y = {min_y, min}.min
    right = rev[min]
    st.set(rev[min], n + 1)
  end
  break if min_x == n
  puts "#{min_x + 1} #{min_y}"
end

class SegTree(T)
  @ar : Array(T)
  @size : Int32
  @op : Proc(T, T, T)
  @zero : T

  def initialize(s : Int32, @op : Proc(T, T, T), @zero : T)
    @size = 1
    while @size < s
      @size *= 2
    end
    @ar = Array.new(@size * 2, @zero)
  end

  def initialize(init : Array(T), @op : Proc(T, T, T), @zero : T)
    @size = 1
    while @size < init.size
      @size *= 2
    end
    @ar = Array.new(@size, @zero)
    @ar.concat(init)
    @ar.concat([@zero] * (@size - init.size))
    (@size - 1).downto(1) do |i|
      @ar[i] = @op.call(@ar[i * 2], @ar[i * 2 + 1])
    end
  end

  def get(lo : Int32, hi : Int32)
    ret = @zero
    bit = 1
    base = @size
    while lo < hi
      if (lo & ((1 << bit) - 1)) != 0
        ret = @op.call(ret, @ar[base + (lo >> (bit - 1))])
        lo += 1 << (bit - 1)
      end
      if (hi & ((1 << bit) - 1)) != 0
        ret = @op.call(ret, @ar[base + (hi >> (bit - 1)) - 1])
        hi -= 1 << (bit - 1)
      end
      bit += 1
      base >>= 1
    end
    return ret
  end

  def set(pos : Int32, v : T)
    base = @size
    @ar[base + pos] = v
    pos >>= 1
    base >>= 1
    while base > 0
      @ar[base + pos] = @op.call(@ar[base * 2 + pos * 2], @ar[base * 2 + pos * 2 + 1])
      pos >>= 1
      base >>= 1
    end
  end
end
0