結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
|
提出日時 | 2020-12-12 15:12:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 394 ms / 2,000 ms |
コード長 | 1,161 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 103,680 KB |
最終ジャッジ日時 | 2024-09-19 21:56:49 |
合計ジャッジ時間 | 8,054 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
from bisect import bisect_left class BIT(): def __init__(self, init): if type(init) == int: self.n = init + 1 self.X = [0] * self.n else: self.n = len(init) + 1 self.X = [0] + init for i in range(1, self.n): if i + (i & -i) < self.n: self.X[i + (i & -i)] += self.X[i] def add(self, i, x=1): i += 1 while i < self.n: self.X[i] += x i += i & (-i) def getsum(self, i): ret = 0 while i != 0: ret += self.X[i] i -= i&(-i) return ret def getrange(self, l, r): return self.getsum(r) - self.getsum(l) def inversion_number(L): bit = BIT(len(L)) ret = 0 for i, a in enumerate(L): ret += i - bit.getsum(a + 1) bit.add(a) return ret N = int(input()) A = list(map(int,input().split())) B = list(map(int,input().split())) b = [] for j in range(N): b.append((B[j],j)) b.sort() l = [] for i in range(N): j = bisect_left(b,(A[i],0)) l.append(b[j][1]) ans = inversion_number(l) print(ans)