結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
コンテスト
ユーザー horiesiniti
提出日時 2018-02-26 08:45:14
言語 Ruby
(3.4.1)
結果
AC  
実行時間 597 ms / 2,500 ms
コード長 1,692 bytes
コンパイル時間 54 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 24,320 KB
最終ジャッジ日時 2024-10-12 13:54:18
合計ジャッジ時間 4,104 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:99: warning: assigned but unused variable - tree
Syntax OK

ソースコード

diff # 

def f3(n,rs,ls)
rs3=n.times.map{0}
ls3=n.times.map{0}
rs.each{|e|
	rs3[e[0]]=1
	rs3[e[1]]=-1
}
ls.each{|e|
	ls3[e[1]]=1
	ls3[e[0]]=-1
}
rc=0
lc=0
ans=0

n.times{|i|
	
	if rs3[i]==0 
		if ls3[i]==1
			ans+=rc
		elsif ls3[i]==-1
			lc-=1
		end
	end
	if ls3[i]==0
		if rs3[i]==1
			ans+=lc
		elsif rs3[i]==-1
			rc-=1
		end
	end
	if rs3[i]==1 && ls3[i]==1
		ans+=rc+1+lc
		rc+=1
		lc+=1
	end
	if rs3[i]==-1 && ls3[i]==-1
		rc-=1
		lc-=1
	end
	#p [i,rc,lc,ans]
}
return ans
end

def fadd(tree,l,r,p1,p2,add)
	if r==l
		tree[p1]+=add
	else
		m=(r+l)/2
		if (p2<=m)
			fadd(tree,l,m,p1*2+1,p2,add)
		else
			fadd(tree,m+1,r,p1*2+2,p2,add)
		end
		tree[p1]+=add
	end
end
def fsum(tree,l,r,p1,r1)
	if r1<l
		return 0
	elsif 0<=l && r<=r1
		return tree[p1]
	else
		ans=0
		m=(l+r)/2
		ans+=fsum(tree,l,m,p1*2+1,r1)
		ans+=fsum(tree,m+1,r,p1*2+2,r1)
		return ans
	end
	return 0
end

def f(n2,n,ds)
	tree=n2.times.map{0}
	n=n-1
	ans=0
	while ds.empty? ==false do
		d1=ds.shift
		while d1.empty? ==false do
			d2=d1.shift
			d=d2[0]
			no=d2[1]
			fadd(tree,0,n,0,no,d)
			if d==-1 
				t=fsum(tree,0,n,0,no)
				if t>0
					ans+=t
				end
			end
		end
		#p [tree,ans,no,d]
	end
	return ans
end

n2=131071
#n2=31
tree=n2.times.map{0}

n=gets.to_i
xs=n.times.map{gets.to_i-1}
xs2=n.times.map{|i|
	[i,xs[i]]
}

rs=xs2.select{|e|
	e[0]<=e[1]	
}
ls=xs2.select{|e|
	e[1]<=e[0]	
}
rs2=xs2.select{|e|
	e[0]<e[1]	
}
ls2=xs2.select{|e|
	e[1]<e[0]	
}


ds=n.times.map{[]}
i=0
#p ds
rs.each{|e|
	ds[e[0]]<<[1,i]
	ds[e[1]]<<[-1,i]
	i+=1
}
ans1=f(n2,n,ds)
ds=n.times.map{[0,0]}
s1=ls.size-1
ls.each{|e|
	
	ds[e[0]]<<[1,s1]
	ds[e[1]]<<[-1,s1]
	s1-=1
}
ds.reverse!
ans2=f(n2,n,ds)
ans3=f3(n,rs2,ls2)
puts ans1+ans2+ans3
0