結果

問題 No.1705 Mode of long array
コンテスト
ユーザー 小野寺健
提出日時 2021-11-30 09:05:44
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,909 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 395 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 52,096 KB
最終ジャッジ日時 2024-07-03 01:25:58
合計ジャッジ時間 14,173 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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