#713017 (Ruby) No.1091 Range Xor Query

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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	84 ms; 12,160 KB
testcase_01	AC	85 ms; 12,160 KB
testcase_02	AC	84 ms; 12,160 KB
testcase_03	AC	292 ms; 24,320 KB
testcase_04	AC	1,234 ms; 22,732 KB
testcase_05	AC	1,388 ms; 31,584 KB
testcase_06	AC	114 ms; 14,592 KB
testcase_07	AC	1,442 ms; 24,420 KB
testcase_08	TLE	-
testcase_09	AC	1,001 ms; 20,428 KB
testcase_10	AC	1,410 ms; 28,264 KB
testcase_11	AC	1,823 ms; 29,644 KB
testcase_12	AC	1,023 ms; 31,440 KB
testcase_13	TLE	-
testcase_14	AC	1,542 ms; 28,364 KB
testcase_15	AC	1,644 ms; 30,952 KB
testcase_16	AC	1,595 ms; 25,796 KB
testcase_17	TLE	-
testcase_18	AC	363 ms; 15,596 KB
testcase_19	AC	413 ms; 24,192 KB
testcase_20	TLE	-
testcase_21	AC	957 ms; 19,072 KB
testcase_22	AC	1,946 ms; 31,732 KB
testcase_23	AC	1,396 ms; 35,164 KB
testcase_24	AC	1,405 ms; 36,008 KB
testcase_25	AC	1,412 ms; 35,836 KB
testcase_26	AC	1,392 ms; 35,852 KB
testcase_27	AC	1,390 ms; 35,032 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{|s| s.to_i}
}

st = SegmentTree.new(a)

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