結果

問題 No.1675 Strange Minimum Query
ユーザー shinichishinichi
提出日時 2021-09-11 17:29:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,984 bytes
コンパイル時間 1,189 ms
コンパイル使用メモリ 86,468 KB
実行使用メモリ 115,892 KB
最終ジャッジ日時 2023-09-05 05:13:22
合計ジャッジ時間 20,319 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
71,336 KB
testcase_01 AC 77 ms
71,236 KB
testcase_02 AC 77 ms
71,320 KB
testcase_03 AC 1,956 ms
109,188 KB
testcase_04 AC 1,906 ms
107,428 KB
testcase_05 AC 268 ms
83,752 KB
testcase_06 TLE -
testcase_07 TLE -
testcase_08 AC 83 ms
75,216 KB
testcase_09 AC 170 ms
79,404 KB
testcase_10 AC 1,347 ms
104,000 KB
testcase_11 AC 291 ms
91,776 KB
testcase_12 AC 1,493 ms
106,336 KB
testcase_13 AC 1,212 ms
115,892 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF, LINF = 10**9, 1 << 59
class LRMQ(object):
    def __init__(self, n):
        self.size = n
        self.binary_roundup()
        self.data = [INF] * (2*self.size-1)
        self.lazy = [INF] * (2*self.size-1)

    def binary_roundup(self):
        self.size -= 1
        i = 1
        while self.size != (self.size | self.size >> i):
            self.size |= self.size >> i
            i += 1
        self.size += 1

    def eval(self, k):
        """lazy配列のk番目に対する操作.呼び出さない"""
        if self.lazy[k] == INF:
            return
        if k < self.size-1:
            self.lazy[2*k+1] = self.lazy[k]
            self.lazy[2*k+2] = self.lazy[k]
        self.data[k] = self.lazy[k]
        self.lazy[k] = INF
        return

    def update(self, left, right, value):
        """[left, right)の半開区間をvalueに更新"""
        assert 0 <= left <= right <= self.size

        def _update(ql, qr, x, k, l, r):
            self.eval(k)
            if ql <= l <= r <= qr:
                self.lazy[k] = x
                self.eval(k)
                return
            if r <= ql or qr <= l:
                return
            _update(ql, qr, x, 2*k+1, l, (l+r)//2)
            _update(ql, qr, x, 2*k+2, (l+r)//2, r)
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])
        return _update(left, right, value, 0, 0, self.size)

    def find_minimum(self, left, right):
        """[left, right)の半開区間の最小値を返す"""
        assert 0 <= left <= right <= self.size

        def query(ql, qr, k, l, r):
            if r <= ql or qr <= l:
                return INF
            self.eval(k)
            if ql <= l <= r <= qr:
                return self.data[k]
            else:
                left_child = query(ql, qr, 2*k+1, l, (l+r)//2)
                right_child = query(ql, qr, 2*k+2, (l+r)//2, r)
                return min(left_child, right_child)
        return query(left, right, 0, 0, self.size)

    def print_tree(self):
        l, r = 0, 0
        while l <= self.size+1:
            print(self.data[l:r+1])
            l = 2*l+1
            r = 2*r+2
        print("=" * 30)

    def print_lazy(self):
        l, r = 0, 0
        while l <= self.size+1:
            print(self.lazy[l:r+1])
            l = 2*l+1
            r = 2*r+2
        print("=" * 30)


if __name__ == '__main__':
    N, Q = map(int, input().split())
    rmq = LRMQ(N)
    query = []
    for _ in range(Q):
        l, r, c = map(int, input().split())
        l -= 1
        query.append((l, r, c))
    query.sort(key=lambda x: x[2])
    for i in range(Q):
        l, r, c = query[i]
        rmq.update(l, r, c)
    for k in range(2*rmq.size-1):
        rmq.eval(k)
    can = True
    for i in range(Q):
        l, r, c = query[i]
        if rmq.find_minimum(l, r) != c:
            can = False
            break
    result = []
    if can:
        print(*rmq.data[rmq.size-1:rmq.size+N-1])
    else:
        print(-1)
0