結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2021-05-21 18:02:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 844 ms / 2,000 ms |
コード長 | 1,703 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 158,788 KB |
最終ジャッジ日時 | 2024-10-10 07:30:40 |
合計ジャッジ時間 | 9,301 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
class segment_tree:__slots__ = ["op_M", "e_M","N","N0","dat"]def __init__(self, N, operator_M, e_M):self.op_M = operator_Mself.e_M = e_Mself.N = Nself.N0 = 1<<(N-1).bit_length()self.dat = [self.e_M]*(2*self.N0)# 長さNの配列 initial で初期化def build(self, initial):assert self.N == len(initial)self.dat[self.N0:self.N0+len(initial)] = initial[:]for k in range(self.N0-1,0,-1):self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])# a_k の値を x に更新def update(self,k,x):k += self.N0self.dat[k] = xk >>= 1while k:self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])k >>= 1# 区間[L,R]をopでまとめるdef query(self,L,R):L += self.N0; R += self.N0 + 1sl = sr = self.e_Mwhile L < R:if R & 1:R -= 1sr = self.op_M(self.dat[R],sr)if L & 1:sl = self.op_M(sl,self.dat[L])L += 1L >>= 1; R >>= 1return self.op_M(sl,sr)def get(self, k): #k番目の値を取得。query[k,k]と同じreturn self.dat[k+self.N0]n = int(input())abc = []M = 1<<30s = set()for _ in range(n):a,b,c = map(int,input().split())s.add(b)abc.append((a*M+(M-b),c))abc.sort(key=lambda x:x[0])sb = sorted(s)zb = {bi:i for i,bi in enumerate(sb)}L = len(sb)B = segment_tree(L,max,0)res = [0]*Lfor ab,c in abc:a,b = divmod(ab,M)b = M-bi = zb[b]v = B.query(0,i-1)+cif B.get(i) < v:B.update(i,v)print(B.dat[1])