#1009244 (PyPy3) No.2873 Kendall's Tau

• 問題: No.2873 Kendall's Tau
• ユーザー: katonyonko
• 提出日時: 2024-09-11 13:53:05
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,541 ms / 4,500 ms
• コード長: 2,387 bytes
• コンパイル時間: 313 ms
• コンパイル使用メモリ: 82,128 KB
• 実行使用メモリ: 230,920 KB
• 最終ジャッジ日時: 2024-09-11 13:53:33
• 合計ジャッジ時間: 26,655 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import io
import sys
from collections import defaultdict, deque, Counter
from itertools import permutations, combinations, accumulate
from heapq import heappush, heappop
from bisect import bisect_right, bisect_left
from math import gcd
import math
_INPUT = """\
6
3
1 4
1 5
9 2
2
1 1
2 2
5
4 4
5 7
0 4
2 10
-6 4
"""
class BIT:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    #合計にはrを含まない
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s
    #pの位置をxという値にセット
    def set(self, p, x):
        self.add(p, -self.sum(p, p+1) + x)
def input():
  return sys.stdin.readline()[:-1]
def solve(test):
  N=int(input())
  data=[list(map(int, input().split())) for _ in range(N)]
  d={x:i for i,x in enumerate(sorted(set([x for x,y in data]+[y for x,y in data])))}
  data=[(d[x],d[y]) for x,y in data]
  data.sort(key=lambda x:(x[0],x[1]))
  bit=BIT(len(d))
  Q=0
  for x,y in data:
    Q+=bit.sum(y+1,len(d))
    bit.add(y,1)
  bit=BIT(len(d))
  data.sort(key=lambda x:(x[0],-x[1]))
  # print(data)
  P=0
  for x,y in data:
    P+=bit.sum(0,y)
    bit.add(y,1)
  C1=Counter([x for x,y in data])
  C2=Counter([y for x,y in data])
  R=sum([(N-C1[x])*C1[x] for x in C1])//2
  S=sum([(N-C2[y])*C2[y] for y in C2])//2
  print((P-Q)/(R*S)**0.5)
def random_input():
  from random import randint,shuffle
  N=randint(1,10)
  M=randint(1,N)
  A=list(range(1,M+1))+[randint(1,M) for _ in range(N-M)]
  shuffle(A)
  return (" ".join(map(str, [N,M]))+"\n"+" ".join(map(str, A))+"\n")*3
def simple_solve():
  return []
def main(test):
  if test==0:
    solve(0)
  elif test==1:
    sys.stdin = io.StringIO(_INPUT)
    case_no=int(input())
    for _ in range(case_no):
      solve(0)
  else:
    for i in range(1000):
      sys.stdin = io.StringIO(random_input())
      x=solve(1)
      y=simple_solve()
      if x!=y:
        print(i,x,y)
        print(*[line for line in sys.stdin],sep='')
        break
#0:提出用、1:与えられたテスト用、2:ストレステスト用
main(0)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX