結果

問題 No.1219 Mancala Combo
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2020-09-09 22:41:03
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,635 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 58,880 KB
最終ジャッジ日時 2024-05-09 19:07:04
合計ジャッジ時間 7,113 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
17,536 KB
testcase_01 AC 74 ms
12,288 KB
testcase_02 AC 70 ms
12,160 KB
testcase_03 AC 71 ms
12,288 KB
testcase_04 AC 598 ms
12,544 KB
testcase_05 AC 243 ms
12,544 KB
testcase_06 AC 146 ms
12,288 KB
testcase_07 AC 273 ms
12,416 KB
testcase_08 AC 272 ms
12,416 KB
testcase_09 AC 72 ms
12,032 KB
testcase_10 AC 74 ms
12,160 KB
testcase_11 AC 189 ms
12,416 KB
testcase_12 AC 92 ms
12,544 KB
testcase_13 AC 144 ms
12,416 KB
testcase_14 AC 71 ms
12,032 KB
testcase_15 AC 71 ms
12,288 KB
testcase_16 AC 72 ms
12,288 KB
testcase_17 TLE -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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)
    @data[k] = lv[0] >= rv[0] ? lv : rv
    return @data[k].dup
  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
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