結果

問題 No.2740 Old Maid
ユーザー sk4rdsk4rd
提出日時 2024-04-20 18:47:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 774 ms / 2,000 ms
コード長 4,205 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 116,576 KB
最終ジャッジ日時 2024-04-20 18:47:39
合計ジャッジ時間 26,345 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 525 ms
115,860 KB
testcase_01 AC 522 ms
116,084 KB
testcase_02 AC 566 ms
115,968 KB
testcase_03 AC 557 ms
115,852 KB
testcase_04 AC 548 ms
116,328 KB
testcase_05 AC 513 ms
116,096 KB
testcase_06 AC 504 ms
115,832 KB
testcase_07 AC 550 ms
116,224 KB
testcase_08 AC 551 ms
116,296 KB
testcase_09 AC 517 ms
115,840 KB
testcase_10 AC 521 ms
116,436 KB
testcase_11 AC 511 ms
115,864 KB
testcase_12 AC 558 ms
108,336 KB
testcase_13 AC 660 ms
111,184 KB
testcase_14 AC 360 ms
85,248 KB
testcase_15 AC 320 ms
85,172 KB
testcase_16 AC 603 ms
98,616 KB
testcase_17 AC 385 ms
85,404 KB
testcase_18 AC 694 ms
108,516 KB
testcase_19 AC 470 ms
89,936 KB
testcase_20 AC 766 ms
112,000 KB
testcase_21 AC 302 ms
84,088 KB
testcase_22 AC 603 ms
99,944 KB
testcase_23 AC 281 ms
83,980 KB
testcase_24 AC 408 ms
91,416 KB
testcase_25 AC 741 ms
112,512 KB
testcase_26 AC 137 ms
77,524 KB
testcase_27 AC 294 ms
81,592 KB
testcase_28 AC 580 ms
98,560 KB
testcase_29 AC 561 ms
100,608 KB
testcase_30 AC 168 ms
78,484 KB
testcase_31 AC 774 ms
116,576 KB
testcase_32 AC 442 ms
91,232 KB
testcase_33 AC 719 ms
112,256 KB
testcase_34 AC 603 ms
96,256 KB
testcase_35 AC 466 ms
89,616 KB
testcase_36 AC 431 ms
91,568 KB
testcase_37 AC 508 ms
93,840 KB
testcase_38 AC 446 ms
89,064 KB
testcase_39 AC 367 ms
84,200 KB
testcase_40 AC 530 ms
101,120 KB
testcase_41 AC 741 ms
111,648 KB
testcase_42 AC 38 ms
52,864 KB
testcase_43 AC 41 ms
54,400 KB
testcase_44 AC 39 ms
54,144 KB
testcase_45 AC 41 ms
53,888 KB
testcase_46 AC 40 ms
53,888 KB
testcase_47 AC 40 ms
53,120 KB
testcase_48 AC 40 ms
53,248 KB
testcase_49 AC 38 ms
53,248 KB
testcase_50 AC 38 ms
53,888 KB
testcase_51 AC 37 ms
53,984 KB
testcase_52 AC 38 ms
53,504 KB
testcase_53 AC 38 ms
54,144 KB
testcase_54 AC 36 ms
53,376 KB
testcase_55 AC 37 ms
53,248 KB
testcase_56 AC 37 ms
53,120 KB
testcase_57 AC 36 ms
53,504 KB
testcase_58 AC 39 ms
54,016 KB
testcase_59 AC 41 ms
54,016 KB
testcase_60 AC 38 ms
53,504 KB
testcase_61 AC 37 ms
53,376 KB
testcase_62 AC 36 ms
52,864 KB
testcase_63 AC 38 ms
53,376 KB
testcase_64 AC 38 ms
53,248 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