結果

問題 No.905 Sorted?
ユーザー 小野寺健小野寺健
提出日時 2021-11-11 12:26:41
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,362 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 11,576 KB
実行使用メモリ 54,516 KB
最終ジャッジ日時 2023-08-14 17:29:43
合計ジャッジ時間 21,155 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
15,120 KB
testcase_01 AC 65 ms
15,256 KB
testcase_02 AC 64 ms
15,016 KB
testcase_03 AC 65 ms
15,128 KB
testcase_04 AC 65 ms
15,352 KB
testcase_05 AC 87 ms
15,948 KB
testcase_06 AC 73 ms
15,336 KB
testcase_07 AC 132 ms
18,272 KB
testcase_08 AC 1,616 ms
40,324 KB
testcase_09 AC 1,175 ms
31,268 KB
testcase_10 AC 1,967 ms
46,792 KB
testcase_11 AC 1,499 ms
48,112 KB
testcase_12 AC 1,637 ms
48,504 KB
testcase_13 AC 1,738 ms
54,516 KB
testcase_14 TLE -
testcase_15 AC 960 ms
47,200 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 AC 67 ms
15,272 KB
testcase_20 AC 67 ms
15,020 KB
testcase_21 AC 66 ms
15,160 KB
testcase_22 AC 65 ms
15,124 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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}
}

ans = []

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

puts ans
0