結果
問題 | No.1675 Strange Minimum Query |
ユーザー | ああいい |
提出日時 | 2022-03-04 12:20:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,477 ms / 2,000 ms |
コード長 | 3,243 bytes |
コンパイル時間 | 436 ms |
コンパイル使用メモリ | 87,036 KB |
実行使用メモリ | 124,192 KB |
最終ジャッジ日時 | 2023-09-25 11:50:48 |
合計ジャッジ時間 | 34,756 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,204 KB |
testcase_01 | AC | 70 ms
71,356 KB |
testcase_02 | AC | 70 ms
71,296 KB |
testcase_03 | AC | 409 ms
101,552 KB |
testcase_04 | AC | 297 ms
97,588 KB |
testcase_05 | AC | 94 ms
80,324 KB |
testcase_06 | AC | 419 ms
102,668 KB |
testcase_07 | AC | 457 ms
112,004 KB |
testcase_08 | AC | 77 ms
75,368 KB |
testcase_09 | AC | 125 ms
77,720 KB |
testcase_10 | AC | 557 ms
101,456 KB |
testcase_11 | AC | 250 ms
88,732 KB |
testcase_12 | AC | 623 ms
102,596 KB |
testcase_13 | AC | 611 ms
109,016 KB |
testcase_14 | AC | 714 ms
117,324 KB |
testcase_15 | AC | 697 ms
119,788 KB |
testcase_16 | AC | 70 ms
71,140 KB |
testcase_17 | AC | 487 ms
88,800 KB |
testcase_18 | AC | 556 ms
89,460 KB |
testcase_19 | AC | 625 ms
97,772 KB |
testcase_20 | AC | 1,071 ms
112,192 KB |
testcase_21 | AC | 971 ms
107,080 KB |
testcase_22 | AC | 1,175 ms
111,176 KB |
testcase_23 | AC | 992 ms
102,380 KB |
testcase_24 | AC | 931 ms
102,484 KB |
testcase_25 | AC | 774 ms
97,744 KB |
testcase_26 | AC | 514 ms
91,264 KB |
testcase_27 | AC | 821 ms
106,072 KB |
testcase_28 | AC | 549 ms
93,636 KB |
testcase_29 | AC | 437 ms
92,496 KB |
testcase_30 | AC | 518 ms
91,780 KB |
testcase_31 | AC | 1,332 ms
111,660 KB |
testcase_32 | AC | 1,424 ms
122,644 KB |
testcase_33 | AC | 1,412 ms
120,992 KB |
testcase_34 | AC | 1,420 ms
121,668 KB |
testcase_35 | AC | 1,477 ms
124,192 KB |
testcase_36 | AC | 1,376 ms
121,836 KB |
ソースコード
#頂点は1-index,下段は0-index class LazySegTree: #単位元と結合と作用をここで定義 Xunit = 0 Aunit = 0 def Xf(self,x,y): return min(x,y) #Xf = max def Af(self,a,b): return max(a,b) #AのXへの作用 def operate(self,x,a): return max(x,a) def __init__(self,N): self.N = N self.X = [self.Xunit] * (N + N) self.A = [self.Aunit] * (N + N) def build(self,seq): for i,x in enumerate(seq,self.N): self.X[i] = x for i in range(self.N-1,0,-1): self.X[i] = self.Xf(self.X[i<<1],self.X[i<<1 | 1]) def eval_at(self,i): return self.operate(self.X[i],self.A[i]) def propagate_at(self,i): self.X[i] = self.eval_at(i) self.A[i<<1] = self.Af(self.A[i<<1],self.A[i]) self.A[i<<1 | 1] = self.Af(self.A[i<<1 | 1],self.A[i]) self.A[i] = self.Aunit def eval(self): for i in range(1,N): self.propagate_at(i) def propagate_above(self,i): H = i.bit_length() - 1 for h in range(H,0,-1): self.propagate_at(i >> h) def recalc_above(self,i): while i > 1: i >>= 1 self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1)) def update(self,i,x): i += self.N self.propagate_above(i) self.X[i] = x self.A[i] = self.Aunit self.recalc_above(i) def fold(self,L = 0,R = -1): if R == -1:R = self.N L += self.N R += self.N self.propagate_above(L // (L & -L)) self.propagate_above(R // (R & -R) -1) vL = 10 ** 9 + 1 vR = 10 ** 9 + 1 while L < R: if L & 1: vL = self.Xf(vL,self.eval_at(L)) L += 1 if R & 1: R -= 1 vR = self.Xf(self.eval_at(R),vR) L >>= 1 R >>= 1 return self.Xf(vL,vR) def operate_range(self,L,R,x): #区間全体に作用させる L += self.N R += self.N L0 = L // (L & -L) R0 = R // (R & -R) - 1 self.propagate_above(L0) self.propagate_above(R0) while L < R: if L & 1: self.A[L] = self.Af(self.A[L],x) L += 1 if R & 1: R -= 1 self.A[R] = self.Af(self.A[R],x) L >>= 1 R >>= 1 self.recalc_above(L0) self.recalc_above(R0) def write(self): print(self.X) def change(self,Xf,Xunit,Af,Aunit,operate): self.Xf = Xf self.Xunit = Xunit self.Af = Af self.Aunit = Aunit self.operate = operate import sys rr = sys.stdin N,Q = map(int,rr.readline().split()) query = [] for _ in range(Q): l,r,b = map(int,rr.readline().split()) query.append((b,l,r)) query.sort(key = lambda s:s[0],reverse = True) seg = LazySegTree(N) for b,l,r in query: num = seg.fold(l-1,r) if num > b: print(-1) exit() seg.operate_range(l-1,r,b) seg.eval() ans = [seg.eval_at(i) for i in range(N,N+N)] for i in range(N): if ans[i] == 0: ans[i] = 10 ** 9 print(*ans)