結果
問題 | No.1826 Fruits Collecting |
ユーザー | customaddone |
提出日時 | 2022-01-28 23:41:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,516 ms / 2,000 ms |
コード長 | 2,881 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 86,952 KB |
実行使用メモリ | 196,624 KB |
最終ジャッジ日時 | 2023-08-28 22:22:03 |
合計ジャッジ時間 | 32,516 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 135 ms
78,532 KB |
testcase_01 | AC | 161 ms
80,188 KB |
testcase_02 | AC | 161 ms
80,012 KB |
testcase_03 | AC | 169 ms
80,244 KB |
testcase_04 | AC | 139 ms
78,760 KB |
testcase_05 | AC | 624 ms
117,764 KB |
testcase_06 | AC | 983 ms
147,312 KB |
testcase_07 | AC | 714 ms
135,376 KB |
testcase_08 | AC | 236 ms
84,352 KB |
testcase_09 | AC | 940 ms
139,732 KB |
testcase_10 | AC | 697 ms
125,340 KB |
testcase_11 | AC | 666 ms
122,648 KB |
testcase_12 | AC | 362 ms
97,132 KB |
testcase_13 | AC | 264 ms
87,644 KB |
testcase_14 | AC | 321 ms
91,208 KB |
testcase_15 | AC | 1,457 ms
196,616 KB |
testcase_16 | AC | 1,444 ms
196,624 KB |
testcase_17 | AC | 1,442 ms
196,036 KB |
testcase_18 | AC | 1,445 ms
195,900 KB |
testcase_19 | AC | 1,500 ms
195,692 KB |
testcase_20 | AC | 1,487 ms
196,176 KB |
testcase_21 | AC | 1,491 ms
196,160 KB |
testcase_22 | AC | 1,465 ms
196,508 KB |
testcase_23 | AC | 1,489 ms
196,416 KB |
testcase_24 | AC | 1,516 ms
195,712 KB |
testcase_25 | AC | 111 ms
72,964 KB |
testcase_26 | AC | 106 ms
72,532 KB |
testcase_27 | AC | 107 ms
73,168 KB |
testcase_28 | AC | 109 ms
72,768 KB |
testcase_29 | AC | 109 ms
72,988 KB |
testcase_30 | AC | 400 ms
105,396 KB |
testcase_31 | AC | 644 ms
125,064 KB |
testcase_32 | AC | 386 ms
103,908 KB |
testcase_33 | AC | 995 ms
161,484 KB |
testcase_34 | AC | 855 ms
145,604 KB |
testcase_35 | AC | 299 ms
93,412 KB |
testcase_36 | AC | 988 ms
163,088 KB |
testcase_37 | AC | 585 ms
140,000 KB |
testcase_38 | AC | 452 ms
128,360 KB |
testcase_39 | AC | 439 ms
126,776 KB |
testcase_40 | AC | 537 ms
140,732 KB |
testcase_41 | AC | 234 ms
91,464 KB |
testcase_42 | AC | 172 ms
81,624 KB |
testcase_43 | AC | 109 ms
73,080 KB |
testcase_44 | AC | 106 ms
72,840 KB |
testcase_45 | AC | 109 ms
72,832 KB |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heapify, heappop, heappush import math from copy import deepcopy from itertools import combinations, permutations, product, combinations_with_replacement from bisect import bisect_left, bisect_right import sys def input(): return sys.stdin.readline().rstrip() def getN(): return int(input()) def getNM(): return map(int, input().split()) def getList(): return list(map(int, input().split())) def getListGraph(): return list(map(lambda x:int(x) - 1, input().split())) def getArray(intn): return [int(input()) for i in range(intn)] mod = 10 ** 9 + 7 MOD = 998244353 sys.setrecursionlimit(10000000) inf = float('inf') eps = 10 ** (-15) dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] ############# # Main Code # ############# # ここの設定を変えて使う #####segfunc##### def segfunc(x, y): return max(x, y) ################# #####ide_ele##### ide_ele = -inf ################# class SegTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num # 配列の値を葉にセット for i in range(n): self.tree[self.num + i] = init_val[i] # 構築していく for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1]) k >>= 1 def query(self, l, r): res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res """ パリティ関係ない とどまれる max移動するかポイントに移動するか というかポイントからポイントへの移動方法は限られる 圧縮セグ木か 離れていく方向で見る 右側を見るときと左側を見る時 """ N = getN() F = [[0, 0, 0]] code = set([-inf, 0, inf]) for _ in range(N): t, x, v = getNM() F.append([x - t, x + t, v]) code.add(x + t) code = sorted(list(set(code))) F.sort(key = lambda i:i[1]) F.sort(key = lambda i:i[0], reverse = True) d = {} for i in range(len(code)): d[code[i]] = i seg = SegTree([-inf] * len(code), segfunc, ide_ele) # セグ木立てる for l, r, v in F: # スタート if l == r == 0: seg.update(d[0], 0) continue seg.update(d[r], seg.query(0, d[r] + 1) + v) print(seg.query(0, len(code)))