結果

問題 No.1219 Mancala Combo
ユーザー TANIGUCHI Kousuke
提出日時 2020-09-09 22:28:48
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,735 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 68,608 KB
最終ジャッジ日時 2024-12-16 10:19:49
合計ジャッジ時間 40,910 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class SegTree
  MIN = [-100_000_000, 0]
  def initialize(data)
    @offset = 1 << data.size.bit_length
    @data = Array.new(@offset * 2, MIN)
    @cmd = Array.new(@offset * 2, 0)
    data.each_with_index do |a,i|
      @data[@offset + i] = [a - i, i]
    end
    
    k = @offset - 1
    while k > 0
      if @data[2 * k][0] >= @data[2 * k + 1][0]
        @data[k] = @data[2 * k].dup
      else
        @data[k] = @data[2 * k + 1].dup
      end
      k -= 1
    end
  end
  
  def apply_cmd(k)
    x = @cmd[k]
    @cmd[k] = 0
    @data[k][0] += x
    if 2 * k + 1 < @data.size
      @cmd[2 * k] += x
      @cmd[2 * k + 1] += x
    end
  end
  
  def range_add(a, b, x, k = 1, l = 0, r = @offset)
    apply_cmd(k)
    return @data[k].dup if b <= l || r <= a
    if a <= l && r <= b
      @cmd[k] += x
      return [@data[k][0] + @cmd[k], @data[k][1]]
    end
    mid = (l + r) / 2
    lv = range_add(a, b, x, 2 * k, l, mid)
    rv = range_add(a, b, x, 2 * k + 1, mid, r)
    if lv[0] >= rv[0]
      @data[k] = lv.dup
    else
      @data[k] = rv.dup
    end
  end
  
  def range_max(a, b, k = 1, l = 0, r = @offset)
    apply_cmd(k)
    return MIN if b <= l || r <= a 
    return @data[k] if a <= l && r <= b
    mid = (l + r) / 2
    lv = range_max(a, b, 2 * k, l, mid)
    rv = range_max(a, b, 2 * k + 1, mid, r)
    return lv[0] >= rv[0] ? lv : rv
  end

  def inspect
    @data[@offset, @offset].inspect + ", @cmd=#{@cmd}"
  end
end

N = gets.to_i
A = gets.split.map(&:to_i)
a0 = A.sum
A.unshift(-a0)
st = SegTree.new(A)

loop do
  v, i = st.range_max(0, N + 1)
  if v.zero? && i.zero?
    puts "Yes"
    break
  elsif v.zero?
    st.range_add(i, i + 1, -i)
    st.range_add(0, i, 1)
  else
    puts "No"
    break
  end
end
0