結果

問題 No.1767 BLUE to RED
ユーザー horitaka1999horitaka1999
提出日時 2021-11-27 00:55:34
言語 PyPy3
(7.3.13)
結果
WA  
実行時間 -
コード長 5,875 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 87,284 KB
実行使用メモリ 162,292 KB
最終ジャッジ日時 2023-09-12 06:14:08
合計ジャッジ時間 9,920 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
71,628 KB
testcase_01 AC 90 ms
71,952 KB
testcase_02 AC 90 ms
71,748 KB
testcase_03 AC 94 ms
71,720 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 97 ms
72,276 KB
testcase_07 AC 115 ms
77,828 KB
testcase_08 AC 132 ms
77,452 KB
testcase_09 AC 365 ms
125,512 KB
testcase_10 AC 418 ms
139,748 KB
testcase_11 AC 358 ms
128,100 KB
testcase_12 AC 343 ms
125,316 KB
testcase_13 WA -
testcase_14 AC 516 ms
161,116 KB
testcase_15 AC 496 ms
159,836 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 521 ms
159,868 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 516 ms
162,292 KB
testcase_23 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def add(self, v):# v を追加(その時点で v はない前提)
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v): # vより真に小さいやつの中での最大値(なければ-1)
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値(なければRoot)
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除(なければ何もしない)
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    #####
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    #####
                    return
        if (not nd.left) and (not nd.right):
            if not prev.left:
                prev.right = None
            elif not prev.right:
                prev.left = None
            else:
                if nd.pivot == prev.left.pivot:
                    prev.left = None
                else:
                    prev.right = None

        elif nd.right:
            # print("type A", v)
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)    
        else:
            # print("type B", v)
            nd.value = self.rightmost(nd.left).value
            self.delete(nd.value - 1, nd.left, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def debug_list(self):
        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(nd.value - 1)
            if nd.right:
                re += debug_node(nd.right)
            return re
        return debug_node(self.root)[:-1]

def diff_list(List):
    rev = []
    for i in range(len(List)):
        if i + 1 < (len(List)):
            tmp = List[i+1] - List[i]
            rev.append(tmp)
    return rev
N,M = map(int,input().split())
from collections import defaultdict,deque
A = list(map(int,input().split()))
INF = float('inf')
A.append(0)
A.sort()
adic = defaultdict(int)
for index in range(len(A)):
    adic[A[index]] = index
B = list(map(int,input().split()))
B.sort()
store = defaultdict(list)
BT = BalancingTree(32)
for a in A:
    BT.add(a)
for index,b in enumerate(B):
    l = BT.find_l(b)
    store[adic[l]].append(b)
ans = 0
for i in range(len(A)):
    if i == len(A) -1:
        store[i].append(A[i])
        store[i].sort()
        if len(store[i]) > 1:
            ans += store[i][-1] - store[i][0]
    else:       
        store[i].append(A[i])
        store[i].append(A[i+1])
        store[i].sort()
        if len(store[i]) > 2:
            maxdis = max(diff_list(store[i]))
            ans += (store[i][-1] - store[i][0]) - maxdis
print(ans)
0