#713019 (Ruby) No.1091 Range Xor Query

• 問題: No.1091 Range Xor Query
• ユーザー: 小野寺健
• 提出日時: 2021-11-05 13:27:50
• 言語: Ruby (3.3.0)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 700 bytes
• コンパイル時間: 234 ms
• コンパイル使用メモリ: 7,424 KB
• 実行使用メモリ: 35,848 KB
• 最終ジャッジ日時: 2024-11-06 03:17:14
• 合計ジャッジ時間: 36,581 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	88 ms; 12,288 KB
testcase_01	AC	86 ms; 12,288 KB
testcase_02	AC	88 ms; 12,288 KB
testcase_03	AC	308 ms; 24,192 KB
testcase_04	AC	1,268 ms; 22,516 KB
testcase_05	AC	1,385 ms; 31,708 KB
testcase_06	AC	116 ms; 14,720 KB
testcase_07	AC	1,440 ms; 24,424 KB
testcase_08	TLE	-
testcase_09	AC	1,006 ms; 20,336 KB
testcase_10	AC	1,424 ms; 28,244 KB
testcase_11	AC	1,907 ms; 29,680 KB
testcase_12	AC	1,014 ms; 31,320 KB
testcase_13	TLE	-
testcase_14	AC	1,537 ms; 28,232 KB
testcase_15	AC	1,653 ms; 30,952 KB
testcase_16	AC	1,607 ms; 25,800 KB
testcase_17	TLE	-
testcase_18	AC	366 ms; 15,448 KB
testcase_19	AC	414 ms; 24,320 KB
testcase_20	TLE	-
testcase_21	AC	977 ms; 19,200 KB
testcase_22	AC	1,980 ms; 32,092 KB
testcase_23	AC	1,407 ms; 34,880 KB
testcase_24	AC	1,398 ms; 35,848 KB
testcase_25	AC	1,400 ms; 34,900 KB
testcase_26	AC	1,395 ms; 35,124 KB
testcase_27	AC	1,413 ms; 35,840 KB

コンパイルメッセージ

Syntax OK

ソースコード

class SegmentTree
	def initialize(v)
		@n = 1
		while @n < v.length do
			@n *= 2
		end
		@node = Array.new(2*@n-1, 0)
		v.each_with_index{|x, i|
			@node[i+@n-1] = x
		}
		(@n-2).downto(0) {|i|
			@node[i] = @node[2*i+1] ^ @node[2*i+2]
		}
	end
	def query(a, b, k=0, l=0, r=@n)
		if r <= a or b <= l then
			return 0
		end
		if a <= l and r <= b then
			return @node[k]
		else
			vl = query(a, b, k * 2 + 1, l, (l + r) / 2)
			vr = query(a, b, k * 2 + 2, (l + r) / 2, r)
			return vl ^ vr
		end
	end
end

N, Q = gets.split(" ").map{|s| s.to_i}
a = gets.split(" ").map{|s| s.to_i}

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

st = SegmentTree.new(a)

q.each {|l, r|
	puts st.query(l-1, r)
}