結果

問題 No.1675 Strange Minimum Query
ユーザー ntuda
提出日時 2025-03-03 21:22:14
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 822 bytes
コンパイル時間 511 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 67,892 KB
最終ジャッジ日時 2025-03-03 21:22:22
合計ジャッジ時間 8,026 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample RE * 3
other RE * 34
権限があれば一括ダウンロードができます

ソースコード

diff #

from atcoder.segtree import SegTree

N,Q = map(int,input().split())
INF = 10 ** 9

LRB = [list(map(int,input().split())) for _ in range(Q)]
LRB.sort(key = lambda x:(x[1],x[0]))
INF = 10 ** 9
prer = -1
prev = INF
A = [INF] * (N + 1)
ST = SegTree(min, INF, A)

for l,r,b in LRB:
    x = ST.prod(l-1,r)
    if x < b:
        print(-1)
        exit()
    elif x > b:
        if prer < l - 1:
            A[l - 1] = b
            ST.set(l - 1, b)
            prer = r - 1
        else:
            if prev > b:
                if prer + 1 < N:
                    A[prer + 1] = b
                    ST.set(prer + 1, b)
                else:
                    print(-1)
                    exit()
            else:
                A[l - 1] = b
                ST.set(l-1,b)
    prev = b
    prer = r - 1

print(*A[:N])






0