結果

問題 No.1219 Mancala Combo
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2020-09-09 22:28:48
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,735 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 11,232 KB
実行使用メモリ 15,492 KB
最終ジャッジ日時 2023-08-22 13:07:39
合計ジャッジ時間 9,500 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
15,308 KB
testcase_01 AC 82 ms
15,140 KB
testcase_02 AC 80 ms
15,144 KB
testcase_03 AC 80 ms
15,156 KB
testcase_04 AC 689 ms
15,464 KB
testcase_05 AC 274 ms
15,492 KB
testcase_06 AC 159 ms
15,288 KB
testcase_07 AC 308 ms
15,384 KB
testcase_08 AC 309 ms
15,372 KB
testcase_09 AC 82 ms
15,088 KB
testcase_10 AC 81 ms
15,140 KB
testcase_11 AC 219 ms
15,324 KB
testcase_12 AC 102 ms
15,360 KB
testcase_13 AC 163 ms
15,340 KB
testcase_14 AC 79 ms
15,012 KB
testcase_15 AC 80 ms
15,096 KB
testcase_16 AC 79 ms
15,148 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)
    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