結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー roknaoroknao
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
権限があれば一括ダウンロードができます

ソースコード

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()
0