結果

問題 No.649 ここでちょっとQK！
ユーザー KohnoKohno
提出日時 2022-07-24 22:25:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 548 ms / 3,000 ms
コード長 5,590 bytes
コンパイル時間 820 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 181,656 KB
最終ジャッジ日時 2024-07-06 17:43:47
合計ジャッジ時間 10,624 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
54,244 KB
testcase_01 AC 37 ms
54,304 KB
testcase_02 AC 36 ms
54,912 KB
testcase_03 AC 219 ms
97,548 KB
testcase_04 AC 420 ms
157,108 KB
testcase_05 AC 419 ms
156,440 KB
testcase_06 AC 322 ms
115,016 KB
testcase_07 AC 38 ms
54,220 KB
testcase_08 AC 37 ms
55,020 KB
testcase_09 AC 38 ms
54,608 KB
testcase_10 AC 37 ms
54,864 KB
testcase_11 AC 37 ms
54,976 KB
testcase_12 AC 311 ms
123,084 KB
testcase_13 AC 311 ms
123,556 KB
testcase_14 AC 311 ms
123,888 KB
testcase_15 AC 333 ms
123,620 KB
testcase_16 AC 317 ms
122,856 KB
testcase_17 AC 331 ms
128,740 KB
testcase_18 AC 361 ms
134,600 KB
testcase_19 AC 396 ms
141,548 KB
testcase_20 AC 409 ms
129,380 KB
testcase_21 AC 448 ms
153,728 KB
testcase_22 AC 458 ms
154,904 KB
testcase_23 AC 474 ms
164,900 KB
testcase_24 AC 501 ms
165,820 KB
testcase_25 AC 548 ms
175,700 KB
testcase_26 AC 547 ms
181,656 KB
testcase_27 AC 62 ms
73,156 KB
testcase_28 AC 61 ms
71,968 KB
testcase_29 AC 60 ms
72,100 KB
testcase_30 AC 281 ms
112,364 KB
testcase_31 AC 273 ms
112,392 KB
testcase_32 AC 35 ms
54,496 KB
testcase_33 AC 34 ms
55,208 KB
testcase_34 AC 35 ms
54,640 KB
testcase_35 AC 35 ms
55,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree(object):
    def __init__(self, v, op, e):
        self._n = len(v)
        self.op = op
        self.e = e

        self.log = SegmentTree._ceil_pow2(self._n)
        self.size = 1 << self.log
        self.d = [self.e] * 2 * self.size
        for i in range(self._n):
            self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    @staticmethod
    def _ceil_pow2(n):
        for x in range(64):
            if 1 << x >= n:
                break
        return x

    def _update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __getitem__(self, p):
        assert 0 <= p < self._n
        return self.d[p + self.size]

    def __setitem__(self, p, x):
        assert 0 <= p < self._n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self._update(p >> i)

    def __str__(self):
        return str(self.d[self.size:])

    def query(self, l, r):
        if l is ...:
            l = 0

        if r is ...:
            r = self._n

        assert 0 <= l <= r <= self._n
        sml = self.e
        smr = self.e
        l += self.size
        r += self.size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def max_right(self, l, f):
        if l is ...:
            l = 0

        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self.size
        sm = self.e

        while True:
            while l & 1 == 0:
                l >>= 1

            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l <<= 1
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size

            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r, f):
        if r is ...:
            r = self._n

        assert 0 <= r <= self._n
        assert f(self.e)

        if r == 0:
            return 0

        r += self.size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r <<= 1
                    r += 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size

            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                break

        return 0

class _CountOrItem(object):
    def __init__(self, _tree_map):
        self._tree = _tree_map._tree
        self._g = _tree_map._g

    def _bind(self, l, r):
        self._l = l
        self._r = r

    def _predicate(self, s):
        return s < self._tree.query(self._l, self._r)

    def count(self):
        return self._tree.query(self._l, self._r)

    def item(self):
        try:
            if self._l is ...:
                i = self._tree.max_right(..., self._predicate)
            else:
                i = self._tree.min_left(..., self._predicate) - 1
        except AssertionError:
            return None
        return self._g[i] if 0 <= i < len(self._g) else None

from operator import add
class LimitedTreeMap(object):
    def __init__(self, domain):
        self._g = sorted(set(domain))
        self._f = {v: k for k, v in enumerate(self._g)}
        self._tree = SegmentTree([0] * len(self._g), add, 0)
        self._count_or_item = _CountOrItem(self)

    def __setitem__(self, p, x):
        p = self._f[p]
        self._tree[p] = x

    def __getitem__(self, p):
        p = self._f[p]
        return self._tree[p]

    def __str__(self):
        return str({v: self._tree[k] for v, k in self._f.items() if self._tree[k]})

    def __repr__(self):
        return str({v: self._tree[k] for v, k in self._f.items() if self._tree[k]})

    def __lt__(self, p):
        p = self._f[p]
        self._count_or_item._bind(..., p)
        return self._count_or_item

    def __le__(self, p):
        p = self._f[p]
        self._count_or_item._bind(..., p + 1)
        return self._count_or_item

    def __gt__(self, p):
        p = self._f[p]
        self._count_or_item._bind(p + 1, ...)
        return self._count_or_item

    def __ge__(self, p):
        p = self._f[p]
        self._count_or_item._bind(p, ...)
        return self._count_or_item

    def k_smallest(self, k):
        i = self._tree.max_right(..., lambda s: s < k + 1)
        return self._g[i] if 0 <= i < len(self._g) else None

    def k_largest(self, k):
        i = self._tree.min_left(..., lambda s: s < k + 1) - 1
        return self._g[i] if 0 <= i < len(self._g) else None

q, k = map(int, input().split())
domain = []
queries = []
for _ in range(q):
    t, *args = map(int, input().split())
    if t == 1:
        domain.append(*args)
    queries.append((t, *args))

tree_map = LimitedTreeMap(domain)
for t, *args in queries:
    if t == 1:
        x, = args
        tree_map[x] += 1
    else:
        x = tree_map.k_smallest(k - 1)
        if x is None:
            x = -1
        else:
            tree_map[x] -= 1
        print(x)
0