結果

問題 No.905 Sorted?
コンテスト
ユーザー 小野寺健
提出日時 2021-11-11 12:19:45
言語 Ruby
(4.0.0)
結果
TLE  
実行時間 -
コード長 1,334 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 129 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 43,648 KB
最終ジャッジ日時 2024-11-22 16:22:33
合計ジャッジ時間 26,589 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 TLE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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