結果

問題 No.1705 Mode of long array
ユーザー 小野寺健小野寺健
提出日時 2021-11-30 09:05:44
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 2,909 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 52,096 KB
最終ジャッジ日時 2024-07-03 01:25:58
合計ジャッジ時間 14,173 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
17,664 KB
testcase_01 AC 81 ms
12,288 KB
testcase_02 AC 79 ms
12,032 KB
testcase_03 AC 131 ms
12,416 KB
testcase_04 AC 158 ms
12,416 KB
testcase_05 AC 143 ms
12,544 KB
testcase_06 AC 332 ms
12,672 KB
testcase_07 AC 249 ms
12,800 KB
testcase_08 AC 230 ms
12,800 KB
testcase_09 AC 182 ms
12,800 KB
testcase_10 AC 184 ms
12,672 KB
testcase_11 AC 317 ms
12,672 KB
testcase_12 AC 246 ms
12,800 KB
testcase_13 AC 2,491 ms
39,552 KB
testcase_14 AC 1,665 ms
28,416 KB
testcase_15 AC 1,578 ms
20,992 KB
testcase_16 AC 1,979 ms
23,808 KB
testcase_17 AC 1,424 ms
20,480 KB
testcase_18 AC 1,081 ms
19,200 KB
testcase_19 AC 2,237 ms
29,056 KB
testcase_20 AC 1,315 ms
23,936 KB
testcase_21 AC 1,885 ms
36,736 KB
testcase_22 AC 2,861 ms
43,904 KB
testcase_23 AC 1,533 ms
19,712 KB
testcase_24 AC 1,452 ms
19,456 KB
testcase_25 AC 1,476 ms
19,456 KB
testcase_26 AC 1,463 ms
19,712 KB
testcase_27 AC 1,525 ms
19,584 KB
testcase_28 AC 1,461 ms
19,584 KB
testcase_29 AC 1,479 ms
19,456 KB
testcase_30 AC 1,536 ms
19,712 KB
testcase_31 AC 1,498 ms
19,712 KB
testcase_32 AC 1,512 ms
19,328 KB
testcase_33 TLE -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class BinaryTree
  attr_accessor :root

  def initialize
    self.root  = nil
  end

  class Node
    attr_accessor :parent, :left, :right, :value

    def initialize(value)
      self.value  = value
      self.parent = nil
      self.left   = nil
      self.right  = nil
    end
  end

  def insert(value)
    node = Node.new(value)

    parent = root
    point = nil
    while parent != nil
      point = parent
      parent = if (point.value <=> node.value) > 0
        point.left
      else
        point.right
      end
    end

    if point != nil
      node.parent = point
      if (point.value <=> node.value) > 0
        point.left = node
      else
        point.right = node
      end
    else
      self.root = node
    end
  end

  def min(node = root)
    node = node.left while node != nil && node.left != nil

    return node
  end

  def max(node = root)
    node = node.right while node != nil && node.right != nil

    return node
  end

  def successor(node)
    return min(node.right) if node.right != nil

    parent = node.parent
    while parent != nil && parent.right.value == node.value
      node   = parent
      parent = parent.parent
    end

    parent
  end

  def search(value)
    node = root
    while node != nil && node.value != value
      node = if (node.value <=> value) > 0
        node.left
      else
        node.right
      end
    end

    node
  end

  def transplant(out_node, node)
    if out_node == root
      out_node.right.parent = node if out_node.right != nil
      out_node.left.parent = node if out_node.left != nil
    else
      if out_node.parent.left == out_node
        out_node.parent.left = node
      else
        out_node.parent.right = node
      end
    end

    node.parent = out_node.parent if node != nil
  end

  def delete(node)
    if node.left == nil
      transplant(node, node.right)

      self.root = node.right if node.parent == nil
    elsif node.right == nil
      transplant(node, node.left)

      self.root = node.left if node.parent == nil
    else
      suc = successor(node)

      if suc.parent != node
        transplant(suc, suc.right)
        suc.right = node.right
        suc.right.parent = suc
      end

      transplant(node, suc)
      suc.left = node.left
      suc.left.parent = suc

      self.root = suc if node.parent == nil
    end
  end
end

N, M = gets.split(" ").map{|s| s.to_i}
a = gets.split(" ").map{|s| s.to_i}
tree = BinaryTree.new
hash = {}
a.each_with_index {|x, i|
	hash[i+1] = x
	tree.insert([x, i+1])
}

Q = gets.to_i
q = []
Q.times {
	q << gets.split(" ").map{|s| s.to_i}
}

q.each {|t, x, y|
	if t == 1 then
		v = hash[x]
		hash[x] = v + y
		node = tree.search([v, x])
		tree.delete(node)
		tree.insert([v + y, x])
	elsif t == 2 then
		v = hash[x]
		hash[x] = v - y
		node = tree.search([v, x])
		tree.delete(node)
		tree.insert([v - y, x])
	else
		max = tree.max
		puts max.value[1]
	end
}
0