結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2020-07-18 01:57:28 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,029 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 80 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 30,620 KB |
最終ジャッジ日時 | 2024-11-30 08:36:37 |
合計ジャッジ時間 | 16,471 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
import sys sys.setrecursionlimit(10 ** 8) input = sys.stdin.readline def main(): N = int(input()) A = [int(x) for x in input().split()] B = [int(x) for x in input().split()] dic = {} for i, b in enumerate(B): dic[b] = i C = [] for a in A: C.append(dic[a]) def segfunc(x,y): return x + y def init(init_val): for i in range(n): seg[i + num - 1] = init_val[i] for i in range(num - 2, -1, -1): seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2]) def update(k, x): k += num - 1 seg[k] = x while k: k = (k - 1) // 2 seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2]) def query(p, q): if q <= p: return ide_ele p += num - 1 q += num - 2 res = ide_ele while q - p > 1: if p & 1 == 0: res = segfunc(res, seg[p]) if q & 1 == 1: res = segfunc(res, seg[q]) q -= 1 p = p // 2 q = (q - 1) // 2 if p == q: res = segfunc(res, seg[p]) else: res = segfunc(segfunc(res, seg[p]), seg[q]) return res # seg tree初期値 (単位元) n = len(C) ide_ele = 0 num = 2 ** (n - 1).bit_length() seg = [ide_ele] * 2 * num ans = 0 for c in C: ans += query(c, N) update(c, 1) print(ans) if __name__ == '__main__': main()