結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 451 ms
77,236 KB
testcase_01 AC 550 ms
78,008 KB
testcase_02 AC 40 ms
54,928 KB
testcase_03 AC 39 ms
53,348 KB
testcase_04 AC 38 ms
54,304 KB
testcase_05 AC 39 ms
53,440 KB
testcase_06 AC 39 ms
53,420 KB
testcase_07 AC 42 ms
58,740 KB
testcase_08 AC 39 ms
54,336 KB
testcase_09 AC 290 ms
77,188 KB
testcase_10 AC 292 ms
76,968 KB
testcase_11 AC 298 ms
76,920 KB
testcase_12 AC 319 ms
76,908 KB
testcase_13 AC 300 ms
76,964 KB
testcase_14 AC 333 ms
77,188 KB
testcase_15 AC 334 ms
77,232 KB
testcase_16 AC 345 ms
77,772 KB
testcase_17 AC 329 ms
77,240 KB
testcase_18 AC 352 ms
76,900 KB
testcase_19 AC 337 ms
77,144 KB
testcase_20 AC 396 ms
77,224 KB
testcase_21 AC 40 ms
53,204 KB
testcase_22 AC 38 ms
54,040 KB
testcase_23 AC 40 ms
53,484 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