#714541 (Ruby) No.905 Sorted?

• 問題: No.905 Sorted?
• ユーザー: 小野寺健
• 提出日時: 2021-11-11 12:19:45
• 言語: Ruby (3.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,334 bytes
• コンパイル時間: 500 ms
• コンパイル使用メモリ: 11,424 KB
• 実行使用メモリ: 48,832 KB
• 最終ジャッジ日時: 2023-08-14 17:20:38
• 合計ジャッジ時間: 23,912 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	66 ms; 15,248 KB
testcase_01	AC	67 ms; 15,240 KB
testcase_02	AC	64 ms; 15,144 KB
testcase_03	AC	68 ms; 15,280 KB
testcase_04	AC	66 ms; 15,276 KB
testcase_05	AC	88 ms; 15,800 KB
testcase_06	AC	77 ms; 15,260 KB
testcase_07	AC	134 ms; 18,288 KB
testcase_08	AC	1,573 ms; 36,212 KB
testcase_09	AC	1,156 ms; 27,600 KB
testcase_10	AC	1,927 ms; 41,104 KB
testcase_11	AC	1,497 ms; 40,308 KB
testcase_12	AC	1,599 ms; 40,664 KB
testcase_13	AC	1,661 ms; 48,832 KB
testcase_14	TLE	-
testcase_15	AC	954 ms; 39,256 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	AC	75 ms; 15,408 KB
testcase_20	AC	66 ms; 15,124 KB
testcase_21	AC	69 ms; 15,324 KB
testcase_22	AC	65 ms; 15,148 KB

コンパイルメッセージ

Syntax OK

ソースコード

N = gets.to_i
A = gets.split(" ").map{|s| s.to_i}

class SegmentTree
	def initialize(n_)
		@n = 1
		while @n < n_ do
			@n *= 2
		end
		@dat = Array.new(2*@n-1) {Array.new}
	end
	def merge(dat0, dat1)
		return nil if dat0 == nil or dat1 == nil
		if dat0.length == 0 then
			return dat1
		elsif dat1.length == 0 then
			return dat0
		elsif (dat0[0] <= dat0[1] and dat1[0] <= dat1[1] and dat0[1] <= dat1[0]) or
			(dat0[0] >= dat0[1] and dat1[0] >= dat1[1] and dat0[1] >= dat1[0]) then
			return [dat0[0], dat1[1]]
		else
			return nil
		end
	end
	def update(k, x)
		k += @n - 1
		@dat[k] = [x, x]
		while k > 0 do
			k = (k - 1) / 2
			@dat[k] = merge(@dat[k * 2 + 1], @dat[k * 2 + 2])
		end
	end
	def query(a, b, k, l, r)
		return [] if r <= a or b <= l
		if a <= l and r <= b then
			return @dat[k]
		else
			vl = query(a, b, k * 2 + 1, l, (l + r) / 2)
			vr = query(a, b, k * 2 + 2, (l + r) / 2, r)
			rv = merge(vl, vr)
			return rv
		end
	end
	def dat
		@dat
	end
	def n
		@n
	end
end

sg = SegmentTree.new(N)

A.each_with_index{|x, i|
	sg.update(i, x)
}

Q = gets.to_i

LR = []

Q.times {
	LR << gets.split(" ").map{|s| s.to_i}
}

LR.each {|l, r|
	q = sg.query(l, r+1, 0, 0, sg.n)
	if q == nil or q.length == 0 then 
		puts "0 0"
	elsif q[0] < q[1] then
		puts "1 0"
	elsif q[0] > q[1] then
		puts "0 1"
	else
		puts "1 1"
	end
}