結果

問題 No.875 Range Mindex Query
ユーザー nagissnagiss
提出日時 2019-09-07 00:16:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 457 ms / 2,000 ms
コード長 1,828 bytes
コンパイル時間 1,475 ms
コンパイル使用メモリ 87,116 KB
実行使用メモリ 101,260 KB
最終ジャッジ日時 2023-09-07 04:04:05
合計ジャッジ時間 6,986 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
71,816 KB
testcase_01 AC 112 ms
76,556 KB
testcase_02 AC 110 ms
77,196 KB
testcase_03 AC 83 ms
75,900 KB
testcase_04 AC 91 ms
76,176 KB
testcase_05 AC 80 ms
75,228 KB
testcase_06 AC 97 ms
76,148 KB
testcase_07 AC 104 ms
76,472 KB
testcase_08 AC 92 ms
76,252 KB
testcase_09 AC 91 ms
76,100 KB
testcase_10 AC 109 ms
77,236 KB
testcase_11 AC 457 ms
95,912 KB
testcase_12 AC 386 ms
89,868 KB
testcase_13 AC 371 ms
101,168 KB
testcase_14 AC 373 ms
98,692 KB
testcase_15 AC 435 ms
101,220 KB
testcase_16 AC 378 ms
101,240 KB
testcase_17 AC 399 ms
101,260 KB
testcase_18 AC 394 ms
101,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]
    def __init__(self, a, default, op):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op
        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i:int, value) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i:int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

N, Q = map(int, input().split())
A = list(map(int, input().split()))
seg = SegmentTree(list(enumerate(A)),
                  (-1, float("inf")),
                  lambda x, y: x if x[1]<y[1] else y)
V = seg.tree
siz = seg.elem_size
Ans = []
for i in range(Q):
    q, l, r = map(int, input().split())
    if q==1:
        l-=1
        r-=1
        (_, al), (_, ar) = V[l+siz], V[r+siz]
        seg.set_value(l, (l, ar))
        seg.set_value(r, (r, al))
    else:
        l-=1
        ami, mi = seg.get_value(l, r)
        Ans.append(ami+1)
print("\n".join(map(str, Ans)))
0