結果
問題 | No.2873 Kendall's Tau |
ユーザー | 👑 p-adic |
提出日時 | 2024-09-07 09:53:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,675 ms / 4,500 ms |
コード長 | 7,557 bytes |
コンパイル時間 | 547 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 263,820 KB |
最終ジャッジ日時 | 2024-09-07 09:54:09 |
合計ジャッジ時間 | 27,955 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,504 KB |
testcase_01 | AC | 40 ms
55,116 KB |
testcase_02 | AC | 41 ms
55,244 KB |
testcase_03 | AC | 41 ms
56,016 KB |
testcase_04 | AC | 41 ms
55,924 KB |
testcase_05 | AC | 40 ms
55,340 KB |
testcase_06 | AC | 42 ms
55,980 KB |
testcase_07 | AC | 1,484 ms
260,708 KB |
testcase_08 | AC | 1,633 ms
262,900 KB |
testcase_09 | AC | 1,484 ms
259,324 KB |
testcase_10 | AC | 1,675 ms
263,820 KB |
testcase_11 | AC | 1,514 ms
261,520 KB |
testcase_12 | AC | 1,623 ms
258,908 KB |
testcase_13 | AC | 530 ms
125,628 KB |
testcase_14 | AC | 1,321 ms
259,524 KB |
testcase_15 | AC | 367 ms
128,712 KB |
testcase_16 | AC | 353 ms
119,148 KB |
testcase_17 | AC | 1,145 ms
238,400 KB |
testcase_18 | AC | 941 ms
182,212 KB |
testcase_19 | AC | 1,117 ms
226,192 KB |
testcase_20 | AC | 416 ms
125,148 KB |
testcase_21 | AC | 978 ms
231,932 KB |
testcase_22 | AC | 478 ms
156,488 KB |
testcase_23 | AC | 986 ms
230,764 KB |
testcase_24 | AC | 254 ms
88,780 KB |
testcase_25 | AC | 348 ms
114,680 KB |
testcase_26 | AC | 1,160 ms
244,396 KB |
testcase_27 | AC | 771 ms
184,212 KB |
testcase_28 | AC | 1,360 ms
246,176 KB |
testcase_29 | AC | 1,511 ms
261,924 KB |
testcase_30 | AC | 328 ms
112,112 KB |
testcase_31 | AC | 427 ms
127,660 KB |
testcase_32 | AC | 974 ms
214,220 KB |
ソースコード
def rec_str(a):return"".join(["[",", ".join(rec_str(x)for x in a),"]"])if isinstance(a,list)else str(a) class BIT: def __init__(self,x): if isinstance(x,int): self.N=x self.F=[0]*(x+1) else: self.N=len(x) self.F=[0]*(self.N+1) for j in R(1,self.N+1): i=j-1 self.F[j]=x[i] k=j-(j&-j) while i>k: self.F[j]+=self.F[i] i-=i&-i def Add(self,i,u): i+=1 while i<=self.N: self.F[i]+=u i+=i&-i def InitialSegmentSum(self,r): assert(r>-2) a=0 i=min(r+1,self.N) while i: a+=self.F[i] i-=i&-i return a class IntervalAddBIT: def __init__(self,N): self.N=N self.F=BIT(N+1) self.G=BIT(N+1) def IntervalAdd(self,l,r,u): self.F.Add(l,-(l-1)*u) self.F.Add(r+1,r*u) self.G.Add(l,u) self.G.Add(r+1,-u) def Add(self,i,u):self.IntervalAdd(i,i,u) def Set(self,i,u):self.Add(i,u-self.Get(i)) def InitialSegmentSum(self,r):return self.F.InitialSegmentSum(r)+r*self.G.InitialSegmentSum(r) def IntervalSum(self,l,r):return self.InitialSegmentSum(r)-self.InitialSegmentSum(l-1) def Get(self,i):return self.IntervalSum(i,i) def list(self):return[self.Get(i)for i in R(self.N)] def __str__(self):return rec_str(self.list()) class NonNegativeLineMultiSubset: def __init__(self,ubound): assert(-1<=ubound) self.ubound=ubound self.bit=IntervalAddBIT(ubound+1) def copy(self): a=__class__([]) a.ubound=self.ubound a.bit=self.bit.copy() return a def insert(self,i,c=1):assert(0<=i<=self.ubound);self.bit.Add(i,c) def IntervalInsert(self,i_start,i_final,c=1):assert(0<=i_start and i_final<=self.ubound);self.bit.IntervalAdd(i_start,i_final,c) def erase(self,i,c=1):self.bit.Add(i,-c) def EraseAll(self,i):self.bit.Set(i,0) def IntervalErase(self,i,c=1):self.bit.IntervalAdd(i_start,i_final,-c) def count(self,i):return self.bit.Get(i)if 0<=i<=self.ubound else 0 def find(self,i):return self.count(i)>0 def InitialSegmentCount(self,i_final):return self.bit.InitialSegmentSum(i_final) def IntervalCount(self,i_start,i_final):return self.bit.IntervalSum(i_start,i_final) #VVV Supported if multiplicities are non-negative def empty(self):return self.InitialSegmentCount(self.ubound)<1 def MaximumLeq(self,i,k=0):#Returning lbound-1 if not exists num=self.InitialSegmentCount(i)-k i-=0 def f(sum,j):return i<=j or num<=sum a=self.Search(f) return a if num>=0 and self.find(a)else 0-1 def MaximumLt(self,i,k=0):return self.MaximumLeq(i-1,k) def MinimumGeq(self,i,k=0):return self.MinimumGt(i-1,k) def MinimumGt(self,i,k=0):#Returning ubound+1 if not exists num=self.InitialSegmentCount(i)+k i-=0 def f(sum,j):return i<j and num<sum return self.Search(f) def Maximum(self,k=0):return self.MaximumLeq(self.ubound,k) def Minimum(self,k=0):return self.MinimumGeq(0,k) def RightEndPointOf(self,i,b=False): if not b and not self.find(i):return i-1 c=i-self.InitialSegmentCount(i) def f(sum,j):return i<=j and sum+c<j return self.Search(f)-1 def LeftEndPointOf(self,i,b=False): if not b and not self.find(i):return i+1 c=i-self.InitialSegmentCount(i) def f(sum,j):return i<=j or(self.find(j)and sum+c==j) return self.Search(f) def ConnectedComponentOf(self,i,b=False): if not b:b=self.find(i) return[self.LeftEndPointOf(i,b),self.RightEndPointOf(i,b)] def GetConnectedComponent(self): a=[] l=self.Minimum() while l<=self.ubound: r=self.RightEndPointOf(l,True) a+=[[l,r]] l=self.MinimumGt(r) return a #AAA Supported if multiplicities are non-negative def __str__(self): s=[] for i in R(0,self.ubound+1): c=self.count(i) if c==1:s+=[str(i)] elif c>0:s+=[str(i)+'x'+str(c)] elif c<0:s+=[str(i)+"x("+str(c)+')'] return '{{'+", ".join(s)+'}}' def lbound(self):return 0 def ubound(self):return self.ubound #private: def Search(self,f):#Computing minimum of j satisfying f(bit.InitialSegmentSum(j),j) or j==bit.N l,r=-1,self.bit.N while l+1<r: m=(l+r)>>1 if f(self.bit.InitialSegmentSum(m),m):r=m else:l=m return r class CompressedLineMultiSubset: def __init__(self,X): self.sorted_list=sorted(set(X)) N=len(self.sorted_list) self.compressed_coordinate={self.sorted_list[i]:i for i in R(N)} self.nnls=NonNegativeLineMultiSubset(N-1) def copy(self): a=__class__([]) a.sorted_list=self.sorted_list[:] a.compressed_coordinate=self.copy() a.nnls=self.nnls.copy() return a def insert(self,i,c=1):self.nnls.insert(self.compressed_coordinate[i],c) def IntervalInsert(self,i_start,i_final,c=1):self.nnls.insert(self.compressed_coordinate[i_start],self.compressed_coordinate[i_final],c) def erase(self,i,c=1):self.nnls.erase(self.compressed_coordinate[i],c) def EraseAll(self,i):self.nnls.EraseAll(self.compressed_coordinate[i]) def IntervalErase(self,i_start,i_final,c=1):self.nnls.erase(self.compressed_coordinate[i_start],self.compressed_coordinate[i_final],c) def count(self,i):return self.nnls.count(self.compressed_coordinate[i])if i in self.compressed_coordinate else 0 def find(self,i):return self.count(i)>0 def InitialSegmentCount(self,i_final):return self.nnls.InitialSegmentCount(self.compressed_coordinate[i_final]) def IntervalCount(self,i_start,i_final):return self.nnls.IntervalCount(self.compressed_coordinate[i_start],self.compressed_coordinate[i_final]) #VVV Supported if multiplicities are non-negative def empty(self):return self.InitialSegmentCount(self.nnls.bit.N-1)<1 def MaximumLeq(self,i,k=0): t=self.nnls.MaximumLeq(self.compressed_coordinate[i],k) return self.sorted_list[t]if t>=0 else None def MaximumLt(self,i,k=0): t=self.nnls.MaximumLt(self.compressed_coordinate[i],k) return self.sorted_list[t]if t>=0 else None def MinimumGeq(self,i,k=0): t=self.nnls.MinimumGeq(self.compressed_coordinate[i],k) return self.sorted_list[t]if t<self.nnls.bit.N else None def MinimumGt(self,i,k=0): t=self.nnls.MinimumGt(self.compressed_coordinate[i],k) return self.sorted_list[t]if t<self.nnls.bit.N else None def Maximum(self,k=0):return self.MaximumLeq(self.sorted_list[-1],k) def Minimum(self,k=0):return self.MinimumGeq(self.sorted_list[0],k) def RightEndPointOf(self,i,b=False): j=self.compressed_coordinate[i] t=self.nnls.RightEndPointOf(j,b) return self.sorted_list[t]if j<=t else i-1 def LeftEndPointOf(self,i,b=False): j=self.compressed_coordinate[i] t=self.nnls.LeftEndPointOf(j,b) return self.sorted_list[t]if t<=j else i+1 def ConnectedComponentOf(self,i,b=False): if not b:b=self.find(i) return[self.LeftEndPointOf(i,b),self.RightEndPointOf(i,b)] def GetConnectedComponent(self): a=[] l=self.Minimum() while l is not None: r=self.RightEndPointOf(l,True) a+=[[l,r]] l=self.MinimumGt(r) return a #AAA Supported if multiplicities are non-negative def __str__(self): s=[] for i in self.sorted_list: c=self.count(i) if c==1:s+=[str(i)] elif c>0:s+=[str(i)+'x'+str(c)] elif c<0:s+=[str(i)+"x("+str(c)+')'] return '{{'+", ".join(s)+'}}' R=range J=lambda:map(int,input().split()) N,*_=J() Dxy={} Dyx={} X=set() Y=set() for i in R(N): x,y=J() X.add(x) Y.add(y) if x in Dxy:Dxy[x]+=[y] else:Dxy[x]=[y] if y in Dyx:Dyx[y]+=[x] else:Dyx[y]=[x] X=sorted(list(X)) for x in X:Dxy[x].sort() query=[10**9] i=0 for x in X: for y in Dxy[x]: query+=[y-1,y,y+1] i+=1 cl=CompressedLineMultiSubset(query) p=q=r=s=0 i=0 for x in X: for y in Dxy[x]: p+=cl.InitialSegmentCount(y-1) q+=cl.IntervalCount(y+1,10**9) for y in Dxy[x]: cl.insert(y) i+=1 for x in X: L=len(Dxy[x]) r+=(N-L)*L for y in Y: L=len(Dyx[y]) s+=(N-L)*L print((p-q)/(r*s)**0.5*2)