結果

問題 No.1675 Strange Minimum Query
ユーザー shinichishinichi
提出日時 2021-09-11 17:29:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,984 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 131,716 KB
最終ジャッジ日時 2024-06-23 01:44:44
合計ジャッジ時間 41,103 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
58,240 KB
testcase_01 AC 36 ms
52,736 KB
testcase_02 AC 36 ms
52,864 KB
testcase_03 AC 1,302 ms
108,388 KB
testcase_04 AC 1,244 ms
101,644 KB
testcase_05 AC 198 ms
82,044 KB
testcase_06 AC 1,588 ms
113,472 KB
testcase_07 AC 1,804 ms
111,792 KB
testcase_08 AC 41 ms
59,008 KB
testcase_09 AC 120 ms
77,092 KB
testcase_10 AC 981 ms
103,568 KB
testcase_11 AC 222 ms
91,076 KB
testcase_12 AC 1,058 ms
104,572 KB
testcase_13 AC 831 ms
115,048 KB
testcase_14 TLE -
testcase_15 WA -
testcase_16 AC 36 ms
52,864 KB
testcase_17 AC 582 ms
86,668 KB
testcase_18 AC 671 ms
87,424 KB
testcase_19 AC 952 ms
100,480 KB
testcase_20 TLE -
testcase_21 AC 1,581 ms
108,236 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 AC 1,906 ms
105,776 KB
testcase_25 AC 1,376 ms
95,072 KB
testcase_26 AC 628 ms
88,656 KB
testcase_27 AC 1,807 ms
108,404 KB
testcase_28 AC 889 ms
97,652 KB
testcase_29 AC 524 ms
94,312 KB
testcase_30 AC 547 ms
89,472 KB
testcase_31 TLE -
testcase_32 TLE -
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