Submission #44669970

---

Source Code Expand

class BIT
	def initialize n
		@n = n # accessing 0..n-1, 1..n internally.
		@a = [0]*(@n+1)
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end

	def inc i
		i += 1
		while i<=@n
			@a[i] += 1
			i += i&-i
		end
	end
end

P = 998244353
(N,),*XY = $<.map{|ln| ln.split.map(&:to_i) }
(X,IX),(Y,IY) = XY.transpose.map{|xs|
	[xs.sort!,xs.each_with_index.to_h]
}
▀ = BIT.new N
F = Hash.new{|h,n| h[n] = 2.pow(n,P)-1 }
p XY.sort_by{_2}.sum{|x,y|
	l = IX[x]
	r = N-l-1
	u = IY[y]
	d = N-u-1
	ul = ▀[l]
	ur = u-ul
	dl = l-ul
	dr = d-dl
	▀.inc l
	next F[N]-F[l]-F[r]-F[u]-F[d]+F[ul]+F[ur]+F[dl]+F[dr]
}%P

Submission Info

Judge Result