結果

問題 No.2740 Old Maid
ユーザー sk4rdsk4rd
提出日時 2024-04-20 18:47:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 878 ms / 2,000 ms
コード長 4,205 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 116,560 KB
最終ジャッジ日時 2024-10-12 15:36:08
合計ジャッジ時間 28,157 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 552 ms
116,560 KB
testcase_01 AC 573 ms
116,092 KB
testcase_02 AC 552 ms
116,324 KB
testcase_03 AC 563 ms
115,840 KB
testcase_04 AC 569 ms
116,244 KB
testcase_05 AC 576 ms
115,736 KB
testcase_06 AC 553 ms
115,880 KB
testcase_07 AC 565 ms
116,020 KB
testcase_08 AC 544 ms
116,528 KB
testcase_09 AC 542 ms
115,848 KB
testcase_10 AC 553 ms
116,208 KB
testcase_11 AC 525 ms
116,268 KB
testcase_12 AC 615 ms
107,892 KB
testcase_13 AC 645 ms
111,160 KB
testcase_14 AC 395 ms
85,384 KB
testcase_15 AC 351 ms
85,456 KB
testcase_16 AC 639 ms
98,892 KB
testcase_17 AC 403 ms
85,668 KB
testcase_18 AC 732 ms
108,544 KB
testcase_19 AC 473 ms
89,884 KB
testcase_20 AC 802 ms
111,928 KB
testcase_21 AC 328 ms
84,024 KB
testcase_22 AC 636 ms
99,688 KB
testcase_23 AC 306 ms
83,728 KB
testcase_24 AC 442 ms
90,708 KB
testcase_25 AC 735 ms
112,036 KB
testcase_26 AC 141 ms
77,276 KB
testcase_27 AC 306 ms
81,860 KB
testcase_28 AC 608 ms
98,140 KB
testcase_29 AC 605 ms
100,804 KB
testcase_30 AC 184 ms
78,360 KB
testcase_31 AC 878 ms
116,236 KB
testcase_32 AC 460 ms
91,088 KB
testcase_33 AC 779 ms
112,336 KB
testcase_34 AC 601 ms
95,976 KB
testcase_35 AC 518 ms
89,844 KB
testcase_36 AC 443 ms
91,812 KB
testcase_37 AC 530 ms
93,836 KB
testcase_38 AC 473 ms
89,124 KB
testcase_39 AC 372 ms
84,364 KB
testcase_40 AC 574 ms
101,156 KB
testcase_41 AC 775 ms
112,260 KB
testcase_42 AC 41 ms
53,376 KB
testcase_43 AC 42 ms
54,104 KB
testcase_44 AC 41 ms
53,616 KB
testcase_45 AC 41 ms
54,476 KB
testcase_46 AC 42 ms
55,644 KB
testcase_47 AC 39 ms
53,080 KB
testcase_48 AC 39 ms
53,168 KB
testcase_49 AC 41 ms
55,452 KB
testcase_50 AC 42 ms
54,568 KB
testcase_51 AC 39 ms
54,044 KB
testcase_52 AC 40 ms
53,620 KB
testcase_53 AC 40 ms
54,388 KB
testcase_54 AC 40 ms
53,708 KB
testcase_55 AC 40 ms
54,236 KB
testcase_56 AC 38 ms
53,284 KB
testcase_57 AC 38 ms
54,524 KB
testcase_58 AC 39 ms
54,516 KB
testcase_59 AC 41 ms
55,192 KB
testcase_60 AC 40 ms
54,944 KB
testcase_61 AC 38 ms
55,000 KB
testcase_62 AC 39 ms
53,912 KB
testcase_63 AC 38 ms
53,672 KB
testcase_64 AC 38 ms
53,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n, self.m = n, 1 << (n-1).bit_length()
        self.data = [ide] * (self.m*2)
        self.func, self.ide = func, ide

    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.m+i] = x
        for i in range(self.m-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.m
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.m; r += self.m 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
  
    def get(self, i):
        return self.data[self.m+i]
    
    def get_data(self):
        return self.data[self.m:self.m+self.n]

    def __setitem__(self, idx, val):
        assert isinstance(idx, int) and -self.n <= idx < self.n
        self.update(idx % self.n, val)

    def __getitem__(self, idx):
        if isinstance(idx, slice):
            l, r, _ = idx.indices(self.n)
            assert l <= r
            return self.query(l, r)
        if isinstance(idx, int) and -self.n <= idx < self.n:
            return self.get(idx % self.n)
        raise AssertionError
class BIT:
    def __init__(self, val):
        if type(val) == int:
            self.n = val
            self.data = [0] * (self.n+1)
        elif type(val) == list:
            self.n = len(val)
            self.data = [0] * (self.n+1)
            self.build(val)
        else: raise TypeError(type(val))
    
    def build(self, data):
        for i in range(1, self.n+1):
            self.data[i] += data[i-1]
            j = i + (i & -i)
            if j <= self.n:
                self.data[j] += self.data[i]
    
    class _Element:
        def __init__(self, outer, i, val):
            self.outer = outer
            self.i = i
            self.val = val
        def __iadd__(self, x):
            self.outer.add(self.i, x)
        def __isub__(self, x):
            self.outer.add(self.i, -x)
        def __str__(self):
            return str(self.val)

    def __getitem__(self, i):
        if not (0 <= i < self.n): raise IndexError(i)
        return self._Element(self, i, self.sum(i, i+1))
    
    def __setitem__(self, i, x):
        if not (0 <= i < self.n): raise IndexError(i)
        if x == None: return
        self.add(i, -self.sum(i, i+1))
        self.add(i, x)
    
    def items(self):
        res, tmp = [0] * self.n, 0
        for i in range(self.n):
            s = self._sum(i+1)
            res[i] = s-tmp
            tmp = s
        return res
     
    def __str__(self):
        return "[" + ", ".join(map(str, self.items())) + "]"
    
    def _sum(self, i):
        assert 0 <= i <= self.n
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def sum(self, i, j=None):
        if j is None: return self._sum(i)
        return self._sum(j) - self._sum(i)
    
    def add(self, i, x):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def lower_bound(self, x):
        cur, s, k = 0, 0, 1 << (self.n.bit_length()-1)
        while k:
            nxt = cur + k 
            if nxt <= self.n and s + self.data[nxt] < x:
                s += self.data[nxt]
                cur = nxt
            k >>= 1
        return cur


n = int(input())
p = list(map(int, input().split()))
d = [0] * (n+1)
for i, x in enumerate(p): d[x] = i
s = SegmentTree(n)
s.build(p)
b = BIT([1] * n)
ans = []

while True:
    rn = b.lower_bound(b.sum(n)-1)+1
    x = s.query(0, rn)
    if x == float("inf"): break
    i = d[x]
    ri = b.sum(i+1)
    j = b.lower_bound(ri+1)
    ans.append(x)
    ans.append(p[j])
    s.update(i, float("inf"))
    s.update(j, float("inf"))
    b[i] -= 1
    b[j] -= 1

print(*ans)
0