結果

問題 No.2759 Take Pictures, Elements?
ユーザー i_taku
提出日時 2024-05-17 21:57:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 623 ms / 2,000 ms
コード長 4,325 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 78,076 KB
最終ジャッジ日時 2025-06-20 13:17:40
合計ジャッジ時間 8,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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