結果
問題 | No.1675 Strange Minimum Query |
ユーザー | kohei2019 |
提出日時 | 2022-07-15 00:06:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,210 bytes |
コンパイル時間 | 407 ms |
コンパイル使用メモリ | 86,884 KB |
実行使用メモリ | 129,124 KB |
最終ジャッジ日時 | 2023-09-08 16:08:38 |
合計ジャッジ時間 | 42,609 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,280 KB |
testcase_01 | AC | 69 ms
71,392 KB |
testcase_02 | AC | 68 ms
71,268 KB |
testcase_03 | AC | 1,034 ms
105,112 KB |
testcase_04 | AC | 916 ms
104,220 KB |
testcase_05 | AC | 203 ms
85,232 KB |
testcase_06 | AC | 1,197 ms
110,348 KB |
testcase_07 | AC | 1,305 ms
113,804 KB |
testcase_08 | AC | 76 ms
75,612 KB |
testcase_09 | AC | 134 ms
78,144 KB |
testcase_10 | AC | 679 ms
104,544 KB |
testcase_11 | AC | 339 ms
94,084 KB |
testcase_12 | AC | 740 ms
105,848 KB |
testcase_13 | AC | 722 ms
116,820 KB |
testcase_14 | AC | 857 ms
125,760 KB |
testcase_15 | AC | 802 ms
129,124 KB |
testcase_16 | AC | 70 ms
71,180 KB |
testcase_17 | AC | 429 ms
87,276 KB |
testcase_18 | AC | 531 ms
90,688 KB |
testcase_19 | AC | 689 ms
100,628 KB |
testcase_20 | AC | 1,235 ms
111,500 KB |
testcase_21 | AC | 1,173 ms
110,348 KB |
testcase_22 | AC | 1,389 ms
116,484 KB |
testcase_23 | AC | 1,246 ms
104,200 KB |
testcase_24 | AC | 1,126 ms
105,108 KB |
testcase_25 | AC | 810 ms
96,424 KB |
testcase_26 | AC | 493 ms
91,636 KB |
testcase_27 | AC | 961 ms
107,816 KB |
testcase_28 | AC | 640 ms
99,852 KB |
testcase_29 | AC | 483 ms
97,068 KB |
testcase_30 | AC | 516 ms
91,492 KB |
testcase_31 | AC | 1,490 ms
113,884 KB |
testcase_32 | AC | 1,835 ms
126,532 KB |
testcase_33 | TLE | - |
testcase_34 | AC | 1,976 ms
126,320 KB |
testcase_35 | AC | 1,687 ms
126,448 KB |
testcase_36 | AC | 1,804 ms
126,356 KB |
ソースコード
import sys import math sys.setrecursionlimit(10**7) class lazysegki(): DEFAULT = { 'min': 1 << 60, 'max': -(1 << 60), } FUNC = { 'min': min, 'max': max, } def __init__(self,N,ls,mode='min'): #葉の数N,要素ls self.default = self.DEFAULT[mode] self.func = self.FUNC[mode] self.N = N self.K = (N-1).bit_length() self.N0 = 1 << self.K self.dat = [self.default]*(2**(self.K+1)) #全体の配列を用意(maxなら-inf,minなら+infで未構築を表現) self.lazy = [None]*(2**(self.K+1)) #遅延評価 for i in range(self.N): #葉の構築 self.dat[2**self.K+i] = ls[i] self.build() def build(self): for j in range(self.N0-1,0,-1): self.dat[j] = self.func(self.dat[j<<1],self.dat[j<<1|1]) #親が持つ条件 def leafvalue(self,x): #x番目の値を出力 return self.query(x,x+1) def gindex(self,l, r): #伝播するインデックス列挙 L = l + self.N0; R = r + self.N0 lm = (L // (L & -L)) >> 1 rm = (R // (R & -R)) >> 1 lsindex = [] while L < R: if R <= rm: lsindex.append(R) if L <= lm: lsindex.append(L) L >>= 1; R >>= 1 while L: lsindex.append(L) L >>= 1 return lsindex def propagates(self,ids): for i in reversed(ids): v = self.lazy[i] if v is None: continue self.lazy[i<<1] = self.dat[i<<1] = self.lazy[i<<1|1] = self.dat[i<<1|1] = v self.lazy[i] = None def update_replace(self,l, r, x): ids = self.gindex(l, r) # 1. トップダウンにlazyの値を伝搬 self.propagates(ids) # 2. 区間[l, r)のdata, lazyの値を更新 L = self.N0 + l; R = self.N0 + r while L < R: if R & 1: R -= 1 self.lazy[R] = self.dat[R] = x if L & 1: self.lazy[L] = self.dat[L] = x L += 1 L >>= 1; R >>= 1 # 3. 伝搬させた区間について、ボトムアップにself.dataの値を伝搬する #print(ids) for i in ids: self.dat[i] = self.func(self.dat[i<<1],self.dat[i<<1|1]) def query(self,l, r): self.propagates(self.gindex(l, r)) L = self.N0 + l R = self.N0 + r vL = self.default vR = self.default while L < R: if L & 1: vL = self.func(vL,self.dat[L]) L += 1 if R & 1: R -= 1 vR = self.func(self.dat[R],vR) L >>= 1 R >>= 1 return self.func(vL,vR) N,Q = map(int,input().split()) lsQ = [] for i in range(Q): l,r,B = map(int,input().split()) lsQ.append((B,l-1,r)) lsQ.sort() ll = [10**9]*(N) LSG = lazysegki(N, ll) for B,l,r in lsQ: LSG.update_replace(l, r, B) for B,l,r in lsQ: v = LSG.query(l, r) if B != v: print(-1) break else: lsans = [LSG.leafvalue(i) for i in range(N)] print(*lsans)