結果

問題 No.1705 Mode of long array
コンテスト
ユーザー 小野寺健
提出日時 2021-11-30 12:49:18
言語 Ruby
(3.4.1)
結果
AC  
実行時間 2,005 ms / 3,000 ms
コード長 742 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-07-03 07:08:56
合計ジャッジ時間 58,988 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class SegmentTree
	def initialize(n)
		@n = 1
		while @n < n do
			@n *= 2
		end
		@dat = Array.new(2*@n-1, Array.new(2, -1))
	end
	def update(k, a)
		i = k
		k += @n - 1
		@dat[k] = [a, i]
		while k > 0 do
			k = (k - 1) / 2
			@dat[k] = [@dat[k * 2 + 1], @dat[k * 2 + 2]].max
		end
	end
	def max
		@dat[0][1] + 1
	end
	def dat(i)
		@dat[i + @n - 1][0]
	end
end

N, M = gets.split(" ").map{|s| s.to_i}
a = gets.split(" ").map{|s| s.to_i}
tree = SegmentTree.new(M)
a.each_with_index {|x, i|
	tree.update(i, x)
}

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

q.each {|t, x, y|
	if t == 1 then
		tree.update(x-1, tree.dat(x-1) + y)
	elsif t == 2 then
		tree.update(x-1, tree.dat(x-1) - y)
	else
		puts tree.max
	end
}
0