結果

問題 No.1219 Mancala Combo
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2020-09-09 22:15:10
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 1,698 bytes
コンパイル時間 534 ms
コンパイル使用メモリ 11,528 KB
実行使用メモリ 48,704 KB
最終ジャッジ日時 2023-08-22 12:51:33
合計ジャッジ時間 7,241 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
15,308 KB
testcase_01 AC 80 ms
15,092 KB
testcase_02 AC 79 ms
15,168 KB
testcase_03 AC 79 ms
15,040 KB
testcase_04 WA -
testcase_05 AC 79 ms
15,296 KB
testcase_06 WA -
testcase_07 AC 79 ms
15,168 KB
testcase_08 WA -
testcase_09 AC 81 ms
15,284 KB
testcase_10 AC 80 ms
15,092 KB
testcase_11 AC 78 ms
15,264 KB
testcase_12 AC 101 ms
15,472 KB
testcase_13 AC 169 ms
15,196 KB
testcase_14 AC 81 ms
15,152 KB
testcase_15 AC 82 ms
15,308 KB
testcase_16 WA -
testcase_17 AC 313 ms
47,292 KB
testcase_18 WA -
testcase_19 AC 216 ms
38,592 KB
testcase_20 WA -
testcase_21 AC 208 ms
37,156 KB
testcase_22 WA -
testcase_23 AC 321 ms
48,068 KB
testcase_24 WA -
testcase_25 AC 211 ms
38,008 KB
testcase_26 WA -
testcase_27 AC 329 ms
48,196 KB
testcase_28 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
    return [range_max(a, b, 2 * k, l, mid), range_max(a, b, 2 * k + 1, mid, r)].max
  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