結果
問題 | No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい |
ユーザー | ああいい |
提出日時 | 2022-03-24 21:04:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,667 ms / 4,000 ms |
コード長 | 3,403 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 190,764 KB |
最終ジャッジ日時 | 2024-04-21 06:11:23 |
合計ジャッジ時間 | 38,054 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,637 ms
183,332 KB |
testcase_01 | AC | 1,253 ms
165,048 KB |
testcase_02 | AC | 567 ms
127,368 KB |
testcase_03 | AC | 1,318 ms
165,300 KB |
testcase_04 | AC | 1,305 ms
166,468 KB |
testcase_05 | AC | 983 ms
144,644 KB |
testcase_06 | AC | 1,667 ms
190,764 KB |
testcase_07 | AC | 665 ms
139,300 KB |
testcase_08 | AC | 595 ms
128,860 KB |
testcase_09 | AC | 1,045 ms
147,720 KB |
testcase_10 | AC | 932 ms
143,780 KB |
testcase_11 | AC | 1,184 ms
157,892 KB |
testcase_12 | AC | 1,059 ms
149,656 KB |
testcase_13 | AC | 538 ms
119,556 KB |
testcase_14 | AC | 721 ms
132,180 KB |
testcase_15 | AC | 277 ms
114,024 KB |
testcase_16 | AC | 1,217 ms
162,632 KB |
testcase_17 | AC | 1,278 ms
164,068 KB |
testcase_18 | AC | 1,325 ms
165,668 KB |
testcase_19 | AC | 519 ms
119,660 KB |
testcase_20 | AC | 677 ms
128,900 KB |
testcase_21 | AC | 630 ms
126,824 KB |
testcase_22 | AC | 1,064 ms
152,184 KB |
testcase_23 | AC | 849 ms
137,912 KB |
testcase_24 | AC | 512 ms
118,856 KB |
testcase_25 | AC | 980 ms
146,652 KB |
testcase_26 | AC | 624 ms
127,976 KB |
testcase_27 | AC | 935 ms
145,396 KB |
testcase_28 | AC | 500 ms
118,268 KB |
testcase_29 | AC | 997 ms
151,816 KB |
testcase_30 | AC | 43 ms
54,784 KB |
testcase_31 | AC | 41 ms
54,144 KB |
testcase_32 | AC | 1,390 ms
173,600 KB |
testcase_33 | AC | 1,476 ms
184,172 KB |
testcase_34 | AC | 668 ms
130,476 KB |
testcase_35 | AC | 44 ms
54,528 KB |
testcase_36 | AC | 45 ms
54,656 KB |
testcase_37 | AC | 53 ms
62,208 KB |
testcase_38 | AC | 61 ms
66,304 KB |
testcase_39 | AC | 134 ms
77,952 KB |
testcase_40 | AC | 145 ms
77,696 KB |
testcase_41 | AC | 228 ms
83,260 KB |
testcase_42 | AC | 229 ms
83,060 KB |
testcase_43 | AC | 197 ms
81,796 KB |
testcase_44 | AC | 200 ms
82,124 KB |
testcase_45 | AC | 181 ms
78,020 KB |
testcase_46 | AC | 472 ms
90,644 KB |
testcase_47 | AC | 480 ms
90,892 KB |
ソースコード
inf = 1 << 20 #頂点は1-index,下段は0-index class LazySegTree: #単位元と結合と作用をここで定義 Xunit = (-1,-inf,-inf,0,0,0) Aunit = (0,0) def Xf(self,x,y): return max(x,y) #Xf = max def Af(self,a,b): return (a[0]+b[0],a[1]+b[1]) #AのXへの作用 def operate(self,x,a): i,j,k,l,r,m = x return (i-a[0],j-a[1],k,l,r,m) 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 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 = self.Xunit vR = self.Xunit 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 N,K = map(int,input().split()) from collections import defaultdict d = defaultdict(list) dd = defaultdict(lambda :[0] * 2) for _ in range(N): s,p,u = map(int,input().split()) d[u].append((s,0,-p,_+1)) now = 0 seq = [] nowi = 0 for u in d: dd[u][0] = now dd[u][1] = now + len(d[u]) now += len(d[u]) for s,num,p,index in d[u]: seq.append((s,num,p,index,nowi,u)) nowi += 1 seg = LazySegTree(N) seg.build(seq) ans = [] for _ in range(K): s,num,p,index,pos,u = seg.fold() ans.append(index-1) seg.operate_range(dd[u][0],dd[u][1],(0,1)) seg.operate_range(pos,pos+1,(inf,0)) print(*ans,sep = "\n")