結果

問題 No.2873 Kendall's Tau
ユーザー flippergo
提出日時 2025-03-15 15:46:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,205 ms / 4,500 ms
コード長 1,505 bytes
コンパイル時間 612 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 230,660 KB
最終ジャッジ日時 2025-03-15 15:47:26
合計ジャッジ時間 35,601 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
Ax = sorted(list(set([A[i][0] for i in range(N)])))
Ay = sorted(list(set([A[i][1] for i in range(N)])))
Dx = {}
Dy = {}
for i in range(len(Ax)):
    Dx[Ax[i]] = i+1
for i in range(len(Ay)):
    Dy[Ay[i]] = i+1
B = sorted([[Dx[A[i][0]],Dy[A[i][1]]] for i in range(N)],key=lambda x:x[0])
Cx = {}
Cy = {}
for i in range(N):
    Cx[B[i][0]] = Cx.get(B[i][0],0)+1
    Cy[B[i][1]] = Cy.get(B[i][1],0)+1
Cx = list(Cx.values())
cumCx = [0]*(len(Cx)+1)
for i in range(1,len(Cx)+1):
    cumCx[i] = cumCx[i-1]+Cx[i-1]
Cy = list(Cy.values())
cumCy = [0]*(len(Cy)+1)
for i in range(1,len(Cy)+1):
    cumCy[i] = cumCy[i-1]+Cy[i-1]
R = 0
for i in range(1,len(cumCx)):
    R += Cx[i-1]*(cumCx[-1]-cumCx[i])
S = 0
for i in range(1,len(cumCy)):
    S += Cy[i-1]*(cumCy[-1]-cumCy[i])
xmax = 0
ymax = 0
for i in range(N):
    x,y = B[i]
    xmax  = max(xmax,x)
    ymax = max(ymax,y)
K = 0
while 2**K<ymax:
    K += 1
M = 2**K
T = [0]*(M+1)
def update(i,a):
    while i<=M:
        T[i] += a
        i += i&(-i)
def cumsum(i):
    cnt = 0
    while i>0:
        cnt += T[i]
        i -= i&(-i)
    return cnt
B = sorted(B,key=lambda x:x[1],reverse=True)
B = sorted(B,key=lambda x:x[0])
P = 0
for i in range(N-1,-1,-1):
    x,y = B[i]
    update(y,1)
    P += N-i-cumsum(y)
B = sorted(B,key=lambda x:x[1])
B = sorted(B,key=lambda x:x[0])
Q = 0
T = [0]*(M+1)
for i in range(N):
    x,y = B[i]
    update(y,1)
    Q += i+1-cumsum(y)
print((P-Q)/(R*S)**0.5)
0