結果
問題 | No.1375 Divide and Update |
ユーザー | あかしあみどり |
提出日時 | 2023-03-02 22:36:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,579 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 81,980 KB |
実行使用メモリ | 227,936 KB |
最終ジャッジ日時 | 2024-09-17 15:29:27 |
合計ジャッジ時間 | 14,650 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
52,736 KB |
testcase_01 | AC | 43 ms
53,504 KB |
testcase_02 | AC | 39 ms
53,120 KB |
testcase_03 | WA | - |
testcase_04 | AC | 40 ms
52,992 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 1,272 ms
216,848 KB |
ソースコード
def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline # import sys # sys.setrecursionlimit(10**8) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input_count = 0 #####segfunc##### def max_segfunc(x, y): return max(x,y) ################# #####segfunc##### def min_segfunc(x, y): return min(x,y) ################# #####ide_ele##### max_ide_ele = float("inf") * -1 min_ide_ele = float("inf") ################# class SegTree: """ init(init_val, ide_ele): 配列init_valで初期化 O(N) update(k, x): k番目の値をxに更新 O(logN) query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN) """ def __init__(self, init_val, segfunc, ide_ele): """ init_val: 配列の初期値 segfunc: 区間にしたい操作 ide_ele: 単位元 n: 要素数 num: n以上の最小の2のべき乗 tree: セグメント木(1-index) """ self.n = len(init_val) self.bitlen = (self.n - 1).bit_length() self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << self.bitlen self.tree = [ide_ele] * 2 * self.num # 配列の値を葉にセット for i in range(self.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番目の値をxに更新 k: index(0-index) x: update value """ 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): """ [l, r)のsegfuncしたものを得る l: index(0-index) r: index(0-index) """ 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 # (累積がx以上のうち最も小さい値, その時のindex)を得る # x以上のものが無ければ None を返す def ge(self, x): bits = 1 base = self.ide_ele if self.tree[1] < x: return (None, None) for i in range(self.bitlen): bits <<= 1 ne = self.segfunc(self.tree[bits], base) #左側のノードまでの累積を計算 if ne < x: base = ne # 右側のノードに進むなら左側までの累積を保存 bits += 1 ind = bits - self.num v = self.tree[bits] return ind, v # (累積がxを超える値のうち最も小さい値, その時のindex)を得る # xを超えるものが無ければ None を返す def gt(self, x): return self.ge(x+1) # (累積がx以下のうち最も大きい値, その時のindex)を得る # x以下のものが無ければ None を返す def le(self, x): if self.tree[self.num] > x: return (None, None) if self.tree[1] < x: return self.n-1, self.tree[self.num-self.n-1] bits = 1 base = self.ide_ele for i in range(self.bitlen): bits <<= 1 ne = self.segfunc(self.tree[bits], base) #左側のノードまでの累積を計算 if ne < x: base = ne # 右側のノードに進むなら左側までの累積を保存 bits += 1 ind = bits - self.num v = self.tree[bits] if self.segfunc(base, v) == x: return ind, v return ind-1, self.tree[self.num - (ind-1)] def lt(self, x): return self.le(x-1) input_count = 0 N,X,Y = mi() A = mi() import itertools as it RA = A[::-1] X_acc = [0]+list(it.accumulate([X-a for a in A])) Y_acc = [0]+list(it.accumulate([Y-a for a in RA])) X_min_tree = SegTree(X_acc, min_segfunc, min_ide_ele) X_max_tree = SegTree(X_acc, max_segfunc, max_ide_ele) Y_min_tree = SegTree(Y_acc, min_segfunc, min_ide_ele) Y_max_tree = SegTree(Y_acc, max_segfunc, max_ide_ele) X_max_dict = {} X_min_dict = {} for i, x in enumerate(X_acc): X_max_dict[x] = i if x not in X_min_dict: X_min_dict[x] = i sumA = sum(A) out = [sumA]*(N-2) Xs = [] for M in range(2, N): temp_max = X_max_tree.query(0,M) ind = X_max_dict[temp_max] temp_min = X_min_tree.query(0,ind+1) if temp_min > 0: temp_min = 0 ans1 = temp_max-temp_min temp_min = X_min_tree.query(0,M) ind = X_min_dict[temp_min] temp_max = X_max_tree.query(ind, M) ans2 = temp_max-temp_min Xs.append(max(ans1, ans2)) Xs Y_acc Y_max_dict = {} Y_min_dict = {} for i, y in enumerate(Y_acc): Y_max_dict[y] = i if y not in Y_min_dict: Y_min_dict[y] = i Ys = [] for M in range(2, N): temp_max = Y_max_tree.query(0,M) ind = Y_max_dict[temp_max] temp_min = Y_min_tree.query(0,ind+1) if temp_min > 0: temp_min = 0 ans1 = temp_max-temp_min temp_min = Y_min_tree.query(0,M) ind = Y_min_dict[temp_min] temp_max = Y_max_tree.query(ind, M) ans2 = temp_max-temp_min if M==2: Ys.append(Y-A[-1]) else: Ys.append(max(ans1, ans2)) for x,y in zip(Xs, Ys[::-1]): print(sumA+x+y)