結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2024-11-08 17:02:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 107,864 KB |
最終ジャッジ日時 | 2024-11-08 17:02:17 |
合計ジャッジ時間 | 7,022 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
import typing class FenwickTree: '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree''' def __init__(self, n: int = 0) -> None: self._n = n self.data = [0] * n def add(self, p: int, x: typing.Any) -> None: assert 0 <= p < self._n p += 1 while p <= self._n: self.data[p - 1] += x p += p & -p def sum(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n return self._sum(right) - self._sum(left) def _sum(self, r: int) -> typing.Any: s = 0 while r > 0: s += self.data[r - 1] r -= r & -r return s N = int(input()) A = [0] + list(map(int,input().split())) B = [0] + list(map(int,input().split())) P = [0] * (N + 1) Q = [0] * (N + 1) for i in range(N + 1): P[A[i]] = i for i in range(N + 1): Q[i] = P[B[i]] ft = FenwickTree(N + 1) cnt = 0 for x in Q: cnt += ft.sum(x, N + 1) ft.add(x, 1) print(cnt)