結果

問題 No.647 明太子
ユーザー 👑 horiesinitihoriesiniti
提出日時 2018-03-11 18:26:07
言語 Ruby
(3.3.0)
結果
AC  
実行時間 584 ms / 4,500 ms
コード長 1,076 bytes
コンパイル時間 54 ms
コンパイル使用メモリ 11,424 KB
実行使用メモリ 31,732 KB
最終ジャッジ日時 2023-09-09 09:41:35
合計ジャッジ時間 5,199 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
15,224 KB
testcase_01 AC 80 ms
15,300 KB
testcase_02 AC 80 ms
15,088 KB
testcase_03 AC 80 ms
15,100 KB
testcase_04 AC 79 ms
15,100 KB
testcase_05 AC 78 ms
15,160 KB
testcase_06 AC 79 ms
15,092 KB
testcase_07 AC 82 ms
15,172 KB
testcase_08 AC 82 ms
15,100 KB
testcase_09 AC 111 ms
15,360 KB
testcase_10 AC 119 ms
15,700 KB
testcase_11 AC 98 ms
15,344 KB
testcase_12 AC 120 ms
15,764 KB
testcase_13 AC 146 ms
15,852 KB
testcase_14 AC 487 ms
31,732 KB
testcase_15 AC 152 ms
17,092 KB
testcase_16 AC 103 ms
16,092 KB
testcase_17 AC 519 ms
30,992 KB
testcase_18 AC 502 ms
31,128 KB
testcase_19 AC 120 ms
15,660 KB
testcase_20 AC 112 ms
15,548 KB
testcase_21 AC 92 ms
15,316 KB
testcase_22 AC 584 ms
16,024 KB
testcase_23 AC 82 ms
15,308 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