結果

問題 No.2759 Take Pictures, Elements?
ユーザー i_takui_taku
提出日時 2024-05-17 21:57:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 591 ms / 2,000 ms
コード長 4,325 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 78,124 KB
最終ジャッジ日時 2024-12-20 13:43:01
合計ジャッジ時間 7,880 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 502 ms
77,372 KB
testcase_01 AC 591 ms
78,124 KB
testcase_02 AC 39 ms
53,300 KB
testcase_03 AC 39 ms
53,072 KB
testcase_04 AC 39 ms
54,308 KB
testcase_05 AC 40 ms
53,228 KB
testcase_06 AC 40 ms
53,644 KB
testcase_07 AC 46 ms
58,376 KB
testcase_08 AC 40 ms
53,820 KB
testcase_09 AC 338 ms
76,904 KB
testcase_10 AC 340 ms
76,760 KB
testcase_11 AC 343 ms
76,896 KB
testcase_12 AC 346 ms
76,900 KB
testcase_13 AC 346 ms
76,856 KB
testcase_14 AC 369 ms
77,076 KB
testcase_15 AC 385 ms
77,032 KB
testcase_16 AC 370 ms
77,648 KB
testcase_17 AC 375 ms
76,832 KB
testcase_18 AC 365 ms
77,316 KB
testcase_19 AC 363 ms
77,052 KB
testcase_20 AC 419 ms
77,308 KB
testcase_21 AC 41 ms
53,288 KB
testcase_22 AC 40 ms
54,132 KB
testcase_23 AC 40 ms
53,012 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self, arr, op, e):
        self._n = len(arr)
        self._op = op
        self._e = e
        self._size = 1 << (self._n - 1).bit_length()
        self._tree = [self._e] * (2 * self._size)
        for i in range(self._n):
            self._tree[self._size + i] = arr[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)
    
    def get(self, k):
        # assert 0 <= k < self._n
        if 0 <= k < self._n:
            return self._tree[k + self._size]
        return self._e
    
    def set(self, k, x):
        # assert 0 <= k < self._n
        if not 0 <= k < self._n:
            return
        k += self._size
        self._tree[k] = x
        while k > 1:
            self._tree[k >> 1] = self._op(self._tree[k], self._tree[k ^ 1])
            k >>= 1

    def all_prod(self):
        return self._tree[1]

    def prod(self, l, r):
        # assert 0 <= l <= r <= self._n
        l = max(l, 0)
        r = min(r, self._n)
        if l > r:
            return self._e
        res_l = res_r = self._e
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                res_l = self._op(res_l, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self._op(self._tree[r], res_r)
            l >>= 1
            r >>= 1
        return self._op(res_l, res_r)

    def max_right(self, l, f):
        '''
        f(op(a[l], a[l + 1], ..., a[r - 1])) = True となる最大の r
        '''
        # assert 0 <= l <= self._n
        if not 0 <= l <= self._n:
            return self._n
        assert f(self._e)
        if l == self._n:
            return self._n

        l += self._size
        res = self._e
        first = True
        while first or (l & -l) != l:
            first = False
            while l % 2 == 0:
                l >>= 1
            if not f(self._op(res, self._tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self._op(res, self._tree[l])):
                        res = self._op(res, self._tree[l])
                        l += 1
                    return l - self._size
                res = self._op(res, self._tree[l])
                l += 1
        return self._n
    
    def min_left(self, r, f):
        '''
        f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l
        '''
        # assert 0 <= r <= self._n
        if not 0 <= r <= self._n:
            return 0
        assert f(self._e)
        if r == 0:
            return 0

        r += self._size
        res = self._e
        first = True
        while first or (r & -r) != r:
            first = False
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not f(self._op(self._tree[r], res)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self._op(self._tree[r], res)):
                        res = self._op(self._tree[r], res)
                        r -= 1
                return r + 1 - self._size
            res = self._op(self._tree[r], res)
        return 0

    def chmin(self, k, x):
        self[k] = min(self[k], x)
    
    def chmax(self, k, x):
        self[k] = max(self[k], x)
    
    def _update(self, k):
        self._tree[k] = self._op(self._tree[2 * k], self._tree[2 * k + 1])
    
    def __getitem__(self, k):
        return self.get(k)
    
    def __setitem__(self, k, x):
        self.set(k, x)
    
    def __iter__(self):
        for i in range(self._n):
            yield self[i]
    
    def __str__(self):
        return str(list(self))
    
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 1 << 60
ans = [INF] * N
l_seg = SegTree([INF] * N, min, INF)
r_seg = SegTree([INF] * N, min, INF)
l_seg[0] = r_seg[0] = 0
ans[0] = 0
for b in B:
    to_inf = []
    for i, a in enumerate(A):
        if a == b:
            best = min(l_seg.prod(0, i) + i, r_seg.prod(i, N) - i)
            ans[i] = best
            l_seg[i] = best - i
            r_seg[i] = best + i
        else:
            to_inf.append(i)
    while to_inf:
        i = to_inf.pop()
        l_seg[i] = r_seg[i] = INF
        ans[i] = INF
print(min(ans))
0