結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | 双六 |
提出日時 | 2020-09-07 03:14:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 794 ms / 2,000 ms |
コード長 | 2,432 bytes |
コンパイル時間 | 399 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 94,720 KB |
最終ジャッジ日時 | 2024-10-02 09:47:33 |
合計ジャッジ時間 | 12,501 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 581 ms
80,192 KB |
testcase_01 | AC | 765 ms
94,552 KB |
testcase_02 | AC | 757 ms
94,336 KB |
testcase_03 | AC | 794 ms
94,720 KB |
testcase_04 | AC | 770 ms
94,464 KB |
testcase_05 | AC | 757 ms
94,720 KB |
testcase_06 | AC | 426 ms
83,584 KB |
testcase_07 | AC | 299 ms
85,404 KB |
testcase_08 | AC | 625 ms
91,392 KB |
testcase_09 | AC | 738 ms
84,868 KB |
testcase_10 | AC | 565 ms
90,880 KB |
testcase_11 | AC | 513 ms
86,272 KB |
testcase_12 | AC | 567 ms
92,932 KB |
testcase_13 | AC | 465 ms
81,808 KB |
testcase_14 | AC | 287 ms
79,016 KB |
testcase_15 | AC | 402 ms
82,112 KB |
testcase_16 | AC | 48 ms
65,152 KB |
testcase_17 | AC | 51 ms
65,792 KB |
testcase_18 | AC | 49 ms
64,000 KB |
testcase_19 | AC | 59 ms
65,536 KB |
testcase_20 | AC | 56 ms
64,116 KB |
ソースコード
import sys; input = sys.stdin.buffer.readline # sys.setrecursionlimit(10**7) from collections import defaultdict con = 10 ** 9 + 7; INF = float("inf") def getlist(): return list(map(int, input().split())) class lazySegTree(object): # N:処理する区間の長さ def __init__(self, N): self.N = N self.LV = (N - 1).bit_length() self.N0 = 2 ** self.LV self.initVal = 0 self.data = [0] * (2 * self.N0) self.lazy = [0] * (2 * self.N0) # 区間クエリの種類 def calc(self, a, b): return max(a, b) # 遅延セグ木の初期化 def initialize(self, A): for i in range(self.N): self.data[self.N0 - 1 + i] = A[i] for i in range(self.N0 - 2, -1, -1): self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2]) # 遅延伝播を行うindexを生成 def gindex(self, l, r): L = (l + self.N0) >> 1; R = (r + self.N0) >> 1 lc = 0 if l & 1 else (L & -L).bit_length() rc = 0 if r & 1 else (R & -R).bit_length() for i in range(self.LV): if rc <= i: yield R if L < R and lc <= i: yield L L >>= 1; R >>= 1 # 遅延伝搬処理 def propagates(self, *ids): for i in reversed(ids): v = self.lazy[i - 1] if not v: continue self.lazy[2 * i - 1] += v; self.lazy[2 * i] += v self.data[2 * i - 1] += v; self.data[2 * i] += v self.lazy[i - 1] = 0 # 区間[l, r]にxを加算 def update(self, l, r, x): *ids, = self.gindex(l, r + 1) self.propagates(*ids) L = self.N0 + l; R = self.N0 + r + 1 while L < R: if R & 1: R -= 1 self.lazy[R - 1] += x; self.data[R - 1] += x if L & 1: self.lazy[L - 1] += x; self.data[L - 1] += x L += 1 L >>= 1; R >>= 1 for i in ids: self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i]) # 区間[l, r]内の最大値を求める def query(self, l, r): self.propagates(*self.gindex(l, r + 1)) L = self.N0 + l; R = self.N0 + r + 1 s = self.initVal while L < R: if R & 1: R -= 1 s = self.calc(s, self.data[R - 1]) if L & 1: s = self.calc(s, self.data[L - 1]) L += 1 L >>= 1; R >>= 1 return s #処理内容 def main(): N = int(input()) T = getlist() M = int(input()) Lis = [T[i] - 3 * i for i in range(N - 1)] lSeg = lazySegTree(N - 1) lSeg.initialize(Lis) for _ in range(M): L, R, D = getlist() L -= 1; R -= 1 lSeg.update(L, R, D) ans = lSeg.query(0, N - 1) print(3 * (N - 1) + ans) if __name__ == '__main__': main()