結果

問題 No.1675 Strange Minimum Query
コンテスト
ユーザー ああ
提出日時 2026-05-17 13:47:45
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 422 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 128,200 KB
最終ジャッジ日時 2026-05-17 13:48:02
合計ジャッジ時間 16,100 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def aa(m):
    while m>1:
        m//=2
        seg[m]=max(seg[m*2],seg[m*2+1])
def bb(l,r):
    res=-1
    while l<r:
        if l&1:
            res=max(res,seg[l]);l+=1
        if r&1:
            r-=1;res=max(res,seg[r])
        l//=2;r//=2
    return res

n,q=map(int,input().split())
x={};y={}
for i in range(q):
    l,r,a=map(int,input().split())
    l-=1
    if a in x:
        x[a]=min(x[a],l);y[a]=max(y[a],r)
    else:
        x[a]=l;y[a]=r
ans=[0]*n
v=1<<n.bit_length()
seg=[-1]*v*2
for i in range(n):
    seg[i+v]=i;aa(i+v)
for i in reversed(sorted(x.keys())):
    l,r=x[i],y[i];c=bb(l+v,r+v)
    if c==-1:
        print(-1);exit()
    ans[c]=i;seg[c+v]=-1;aa(c+v)
    while 1:
        c=bb(l+v,r+v)
        if c==-1:
            break
        ans[c]=i;seg[c+v]=-1;aa(c+v);a-=1
for i in range(n):
    if ans[i]:
        continue
    ans[i]=1
print(" ".join(map(str,ans)))
0