結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:38:14 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 426 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 30,852 KB |
最終ジャッジ日時 | 2024-11-29 22:23:16 |
合計ジャッジ時間 | 11,061 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
n=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))DICT=dict()for i in range(n):DICT[B[i]]=i+1for i in range(n):A[i]=DICT[A[i]]LEN=len(A)MAX=max(A)MIN=min(A)BIT=[0]*(MAX-MIN+2) # 出現回数をbit indexed treeの形でもっておく.def update(v,w): # index vにwを加えるwhile v<=MAX-MIN+1:BIT[v]+=wv+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4def getvalue(v): # MIN~vの区間の和を求めるANS=0while v!=0:ANS+=BIT[v]v-=(v&(-v)) # たとえばv=3→v=2へreturn ANSANS=0for i in range(LEN): # A[0],A[1],...とBITを更新しながら,各A[i]について転倒数を求める.bit_ai=A[i]-MIN+1 # A[i]がBITの中で何番目かANS+=i # 今まで出現した個数.ANS-=getvalue(bit_ai) # 今まで出現した中で,MIN~bit_aiの個数を減らす.# bit_ai~MAXの出現個数が転倒数update(bit_ai,1)print(ANS)