結果

問題 No.1705 Mode of long array
ユーザー 小野寺健小野寺健
提出日時 2021-11-30 09:05:44
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 2,909 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 11,488 KB
実行使用メモリ 50,116 KB
最終ジャッジ日時 2023-09-16 00:19:15
合計ジャッジ時間 47,837 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
19,348 KB
testcase_01 AC 83 ms
15,148 KB
testcase_02 AC 83 ms
15,228 KB
testcase_03 AC 138 ms
15,272 KB
testcase_04 AC 161 ms
15,288 KB
testcase_05 AC 146 ms
15,472 KB
testcase_06 AC 334 ms
15,848 KB
testcase_07 AC 253 ms
16,012 KB
testcase_08 AC 224 ms
15,940 KB
testcase_09 AC 181 ms
15,952 KB
testcase_10 AC 184 ms
15,864 KB
testcase_11 AC 316 ms
15,716 KB
testcase_12 AC 248 ms
15,828 KB
testcase_13 AC 2,518 ms
38,236 KB
testcase_14 AC 1,704 ms
29,476 KB
testcase_15 AC 1,612 ms
25,684 KB
testcase_16 AC 2,018 ms
27,508 KB
testcase_17 AC 1,387 ms
23,496 KB
testcase_18 AC 1,106 ms
23,748 KB
testcase_19 AC 2,309 ms
30,124 KB
testcase_20 AC 1,342 ms
26,400 KB
testcase_21 AC 1,945 ms
32,916 KB
testcase_22 AC 2,945 ms
42,452 KB
testcase_23 AC 1,486 ms
26,604 KB
testcase_24 AC 1,438 ms
26,408 KB
testcase_25 AC 1,456 ms
26,388 KB
testcase_26 AC 1,460 ms
26,548 KB
testcase_27 AC 1,519 ms
26,412 KB
testcase_28 AC 1,463 ms
26,356 KB
testcase_29 AC 1,477 ms
26,304 KB
testcase_30 AC 1,494 ms
25,852 KB
testcase_31 AC 1,504 ms
26,452 KB
testcase_32 AC 1,510 ms
26,208 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