結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー roknao
提出日時 2020-09-27 21:08:01
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,120 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 88,960 KB
最終ジャッジ日時 2024-06-30 12:55:18
合計ジャッジ時間 7,750 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 5
other RE * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from functools import reduce
from fractions import gcd
from collections import defaultdict
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")
def segfunc(x, y):
    return x + y
class SegmentTree:
    def __init__(self, arr, ini):
        size = len(arr)
        self.ini = ini
        self.n = 2 ** (size-1).bit_length()
        self.node = [self.ini] * (2*self.n - 1)
        # print(self.n)
        # print(self.node)
        for i in range(size):
            self.node[i+self.n-1] = arr[i]
        for i in reversed(range(self.n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2])
    
    def add(self, x, val):
        x += (self.n - 1)
        self.node[x] += val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2])
    
    def get_point(self, x):
        return self.node[x + self.n - 1]
    
    def query(self, a, b):
        res = self.ini
        l = self.n - 1 + a
        r = self.n - 1 + (b-1)
        
        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break
            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1
        
        return res
# 処理内容
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    d = defaultdict(int)
    for i in range(N):
        d[A[i]] = i
    C = [0] * N
    for i in range(N):
        C[i] = d[B[i]]
    seg = SegmentTree([0]*100010, 0)
    ans = 0
    for i in range(N):
        seg.add(C[i], 1)
        ans += i + 1 - seg.query(0, C[i]+1)
    
    print(ans)
if __name__ == '__main__':
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0