結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
|
提出日時 | 2020-07-18 17:46:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 106,112 KB |
最終ジャッジ日時 | 2024-11-30 21:55:58 |
合計ジャッジ時間 | 5,922 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
class segtree: def __init__(self,_n): self.n=1 while self.n<_n: self.n<<=1 self.dat=[0]*(self.n<<1) for i in range(self.n-1,0,-1): self.dat[i]=self.dat[i<<1]+self.dat[i<<1|1] def update(self,k,a): k+=self.n self.dat[k]+=a while 1<k: k>>=1 self.dat[k]=self.dat[k<<1]+self.dat[k<<1|1] def value(self,l,r): res=0 l+=self.n r+=self.n while l<r: if l&1: res+=self.dat[l] l+=1 if r&1: r-=1 res+=self.dat[r] l>>=1 r>>=1 return res def main(): import sys input=sys.stdin.readline n=int(input()) a=(lambda x:[i-1 for i in x])(list(map(int,input().split()))) b=(lambda x:[i-1 for i in x])(list(map(int,input().split()))) p=[0]*n for i in range(n): p[b[i]]=i for i in range(n): a[i]=p[a[i]] ans=0 seg=segtree(n) for i in a: ans+=seg.value(i+1,n) seg.update(i,1) print(ans) if __name__ == '__main__': main()