結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー | None |
提出日時 | 2021-02-25 13:29:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 1,648 bytes |
コンパイル時間 | 830 ms |
コンパイル使用メモリ | 81,480 KB |
実行使用メモリ | 150,960 KB |
最終ジャッジ日時 | 2023-10-26 03:49:44 |
合計ジャッジ時間 | 9,462 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
77,192 KB |
testcase_01 | AC | 37 ms
53,372 KB |
testcase_02 | AC | 37 ms
53,372 KB |
testcase_03 | AC | 230 ms
136,768 KB |
testcase_04 | AC | 251 ms
150,960 KB |
testcase_05 | AC | 214 ms
135,968 KB |
testcase_06 | AC | 191 ms
125,816 KB |
testcase_07 | AC | 235 ms
150,704 KB |
testcase_08 | AC | 63 ms
76,604 KB |
testcase_09 | AC | 129 ms
114,228 KB |
testcase_10 | AC | 188 ms
150,344 KB |
testcase_11 | AC | 37 ms
53,372 KB |
testcase_12 | AC | 245 ms
150,872 KB |
testcase_13 | AC | 238 ms
150,872 KB |
testcase_14 | AC | 237 ms
150,876 KB |
testcase_15 | AC | 37 ms
53,372 KB |
testcase_16 | AC | 37 ms
53,372 KB |
testcase_17 | AC | 36 ms
53,372 KB |
testcase_18 | AC | 36 ms
53,372 KB |
testcase_19 | AC | 37 ms
53,372 KB |
testcase_20 | AC | 37 ms
53,372 KB |
testcase_21 | AC | 37 ms
53,372 KB |
testcase_22 | AC | 38 ms
53,372 KB |
testcase_23 | AC | 68 ms
77,216 KB |
testcase_24 | AC | 112 ms
93,256 KB |
testcase_25 | AC | 190 ms
125,404 KB |
testcase_26 | AC | 87 ms
85,884 KB |
testcase_27 | AC | 127 ms
101,632 KB |
testcase_28 | AC | 158 ms
112,272 KB |
testcase_29 | AC | 197 ms
125,848 KB |
testcase_30 | AC | 231 ms
150,200 KB |
testcase_31 | AC | 95 ms
87,908 KB |
testcase_32 | AC | 81 ms
83,596 KB |
testcase_33 | AC | 170 ms
136,340 KB |
testcase_34 | AC | 38 ms
53,372 KB |
testcase_35 | AC | 37 ms
53,372 KB |
testcase_36 | AC | 39 ms
53,372 KB |
testcase_37 | AC | 38 ms
53,372 KB |
testcase_38 | AC | 38 ms
53,372 KB |
testcase_39 | AC | 38 ms
53,372 KB |
ソースコード
class Bit: def __init__(self, n): self.n = n self.tree = [0]*(n+1) self.el = [0]*(n+1) self.depth = n.bit_length() - 1 def sum(self, i): """ 区間[0,i) の総和を求める """ s = 0 i -= 1 while i >= 0: s += self.tree[i] i = (i & (i + 1) )- 1 return s def add(self, i, x): self.el[i] += x while i < self.n: self.tree[i] += x i |= i + 1 class BitSet2: """ 座標圧縮が必要な場合 """ def __init__(self, data, A=[]): """ BitSetに入り得る値を先読みした物を data に格納 """ self.data = sorted(list(set(data))) self.n = len(self.data) self.p = Bit(self.n + 1) self.size = 0 self.flip = 0 self.code = {} self.decode = {} for i, b in enumerate(self.data): self.code[b] = i self.decode[i] = b for a in A: self.add(a) def add(self,x): self.p.add(self.code[x], 1) self.size += 1 self.flip += self.size - self.p.sum(self.code[x]+1) def remove(self,x): self.p.add(x, -1) self.size -= 1 def flip_counter(self): return self.flip #################################################################################################### import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) decode=A[:] code={x:i for i,x in enumerate(decode)} C=[] for b in B: C.append(code[b]) BS = BitSet2(C,C) print(BS.flip_counter())