結果

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

ソースコード

diff # 

from functools import reduce
from fractions import gcd
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()))
    for i in range(N):
        A[i] -= 1
        B[i] -= 1

    C = [0] * N
    for i in range(N):
        C[B[i]] = A[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)
    
    print(ans)


if __name__ == '__main__':
    main()
0