結果

問題 No.905 Sorted?
ユーザー 小野寺健小野寺健
提出日時 2021-11-11 12:26:41
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,362 bytes
コンパイル時間 50 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 49,088 KB
最終ジャッジ日時 2024-11-22 16:30:53
合計ジャッジ時間 25,246 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
12,288 KB
testcase_01 AC 82 ms
12,032 KB
testcase_02 AC 76 ms
12,032 KB
testcase_03 AC 80 ms
12,160 KB
testcase_04 AC 77 ms
12,288 KB
testcase_05 AC 105 ms
12,928 KB
testcase_06 AC 99 ms
12,672 KB
testcase_07 AC 166 ms
14,464 KB
testcase_08 AC 1,942 ms
37,120 KB
testcase_09 AC 1,353 ms
28,124 KB
testcase_10 TLE -
testcase_11 AC 1,858 ms
43,520 KB
testcase_12 AC 1,932 ms
43,392 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 AC 1,117 ms
44,160 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 AC 79 ms
12,160 KB
testcase_20 AC 78 ms
12,160 KB
testcase_21 AC 76 ms
12,160 KB
testcase_22 AC 77 ms
12,160 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