結果

問題 No.647 明太子
ユーザー horiesinitihoriesiniti
提出日時 2018-03-11 18:26:07
言語 Ruby
(3.3.0)
結果
AC  
実行時間 610 ms / 4,500 ms
コード長 1,076 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 29,312 KB
最終ジャッジ日時 2024-06-27 02:50:44
合計ジャッジ時間 5,333 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
12,288 KB
testcase_01 AC 93 ms
12,288 KB
testcase_02 AC 85 ms
12,160 KB
testcase_03 AC 85 ms
12,160 KB
testcase_04 AC 83 ms
12,288 KB
testcase_05 AC 84 ms
12,288 KB
testcase_06 AC 87 ms
12,288 KB
testcase_07 AC 91 ms
12,032 KB
testcase_08 AC 90 ms
12,160 KB
testcase_09 AC 122 ms
12,416 KB
testcase_10 AC 130 ms
12,416 KB
testcase_11 AC 107 ms
12,288 KB
testcase_12 AC 130 ms
12,416 KB
testcase_13 AC 157 ms
12,928 KB
testcase_14 AC 502 ms
29,056 KB
testcase_15 AC 161 ms
14,464 KB
testcase_16 AC 113 ms
12,928 KB
testcase_17 AC 545 ms
29,312 KB
testcase_18 AC 537 ms
29,312 KB
testcase_19 AC 135 ms
12,800 KB
testcase_20 AC 126 ms
12,672 KB
testcase_21 AC 104 ms
12,416 KB
testcase_22 AC 610 ms
12,800 KB
testcase_23 AC 94 ms
12,288 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def f(x,l,r)
	if l==r
		$hs[[l,r]]+=1
	elsif (l<=x&&x<=r)
		$hs[[l,r]]+=1
		m=(l+r)/2
		f(x,l,m)
		f(x,m+1,r)
	end
end
def sum(l,r,l2,r2)
	if $hs.key?([l,r])==false
		return 0
	else
		if r<l2
			return 0
		end
		if r2<l 
			return 0
		end
		if(l2<=l&&r<=r2)
			return $hs[[l,r]]
		end
		m=(l+r)/2
		res=sum(l,m,l2,r2)
		res+=sum(m+1,r,l2,r2)
		return res
	end
end

n=gets.to_i
ab=[]
n.times{
	a,b=gets.split.map{|e| e.to_i}
	ab<<[a,-b]
}
m=gets.to_i
xy=[]
no=1
m.times{
	x,y=gets.split.map{|e| e.to_i}
	xy<<[x,-y,no]
	no+=1
}
ab=ab.sort.reverse
xy=xy.sort.reverse
$hs=Hash.new(0)
rmax=134217727
$hs[[0,rmax]]=0

ans=[]

while ab.empty? == false && xy.empty? == false
	while ab.empty? ==false && (xy.empty? ==true || ab[0][0]>=xy[0][0])
		f(-ab.shift[1],0,rmax)
	end
	
	while xy.empty? ==false && (ab.empty? ==true || xy[0][0]>ab[0][0])
		e1=xy.shift
		ans<<[sum(0,rmax,0,-e1[1]),e1[2]]
	end
end
ans=ans.sort.reverse
ans2=[]
if ans.empty? == true || ans[0][0]==0
	puts 0
else
	e=ans[0][0]
	while ans.empty? == false && ans[0][0]==e
		ans2<<ans.shift[1]
	end
	puts ans2.sort
end
0