結果
問題 |
No.1282 Display Elements
|
ユーザー |
![]() |
提出日時 | 2020-11-06 22:38:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 669 ms / 2,000 ms |
コード長 | 956 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 126,712 KB |
最終ジャッジ日時 | 2024-07-22 13:21:38 |
合計ジャッジ時間 | 5,708 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
class BIT: def __init__(self, n): self.n = n self.data = [0]*(n+1) def to_sum(self, i): s = 0 while i > 0: s += self.data[i] i -= (i & -i) return s def add(self, i, x): while i <= self.n: self.data[i] += x i += (i & -i) def get(self, i, j): return self.to_sum(j)-self.to_sum(i-1) N = int(input()) A = list(map(int,input().split())) B = list(map(int,input().split())) C = [] for i in range(N): C.append((A[i],"A",i)) C.append((B[i],"B",i)) C.sort() AA = [-1 for _ in range(N)]; BB = [-1 for _ in range(N)] cnt = 0 prev = 0 for i in range(2*N): ID = C[i][2] if C[i][0] != prev: cnt += 1 prev = C[i][0] if C[i][1] == "A": AA[ID] = cnt else: BB[ID] = cnt #print(AA) #print(BB) AA.sort() Tree = BIT(2*N) ans = 0 for i in range(N): Tree.add(BB[i],1) if AA[i] > 1: ans += Tree.get(1,AA[i]-1) print(ans)