結果

問題 No.647 明太子
コンテスト
ユーザー horiesiniti
提出日時 2018-03-11 18:26:07
言語 Ruby
(3.4.1)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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