結果

問題 No.2740 Old Maid
ユーザー sk4rd
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

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