結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2023-09-05 08:55:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,175 ms / 2,000 ms |
コード長 | 1,667 bytes |
コンパイル時間 | 186 ms |
コンパイル使用メモリ | 82,552 KB |
実行使用メモリ | 176,092 KB |
最終ジャッジ日時 | 2024-06-23 04:50:23 |
合計ジャッジ時間 | 12,217 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
import sysinput = sys.stdin.readlinefrom copy import *from bisect import *def compress(lst):"""B: lstを座圧したリストD: indexから元の値を取得する辞書"""B = []D = dict()vals = deepcopy(lst)vals = list(set(vals))vals.sort()for i in range(len(lst)):ind = bisect_left(vals, lst[i])B.append(ind)for i in range(len(B)):D[lst[i]] = B[i]return B, D, valsclass SegmentTree:def __init__(self, size, f=max, default=0):self.size = 2**(size-1).bit_length()self.default = defaultself.dat = [default]*(self.size*2)self.f = fdef update(self, i, x):i += self.sizeself.dat[i] = xwhile i > 0:i >>= 1self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])def query(self, l, r):l += self.sizer += self.sizelres, rres = self.default, self.defaultwhile l < r:if l & 1:lres = self.f(lres, self.dat[l])l += 1if r & 1:r -= 1rres = self.f(self.dat[r], rres)l >>= 1r >>= 1res = self.f(lres, rres)return resN = int(input())A, B, C = [0] * N, [0] * N, [0] * Nfor i in range(N):A[i], B[i], C[i] = map(int, input().split())A, _, _ = compress(A)B, _, _ = compress(B)D = []for i in range(N):D.append((A[i], -B[i], C[i]))D.sort()T = SegmentTree(N + 5)for a, b, c in D:b = -bv = T.query(0, b) + cv = max(v, T.query(b, b + 1))T.update(b, v)print(T.query(0, N + 5))