#714541 (Ruby) No.905 Sorted?

• 問題: No.905 Sorted?
• ユーザー: 小野寺健
• 提出日時: 2021-11-11 12:19:45
• 言語: Ruby (3.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,334 bytes
• コンパイル時間: 129 ms
• コンパイル使用メモリ: 7,424 KB
• 実行使用メモリ: 43,648 KB
• 最終ジャッジ日時: 2024-11-22 16:22:33
• 合計ジャッジ時間: 26,589 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	84 ms; 12,288 KB
testcase_01	AC	80 ms; 12,032 KB
testcase_02	AC	83 ms; 12,416 KB
testcase_03	AC	87 ms; 12,416 KB
testcase_04	AC	80 ms; 12,288 KB
testcase_05	AC	105 ms; 12,928 KB
testcase_06	AC	90 ms; 12,544 KB
testcase_07	AC	169 ms; 14,464 KB
testcase_08	AC	1,904 ms; 32,000 KB
testcase_09	AC	1,406 ms; 24,400 KB
testcase_10	TLE	-
testcase_11	AC	1,786 ms; 36,480 KB
testcase_12	TLE	-
testcase_13	AC	1,991 ms; 42,816 KB
testcase_14	TLE	-
testcase_15	AC	1,160 ms; 43,648 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	AC	81 ms; 12,032 KB
testcase_20	AC	83 ms; 12,288 KB
testcase_21	AC	81 ms; 12,160 KB
testcase_22	AC	81 ms; 12,160 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
}