結果
問題 | No.2640 traO Stamps |
ユーザー |
👑 |
提出日時 | 2024-02-19 21:41:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 596 ms / 2,000 ms |
コード長 | 3,680 bytes |
コンパイル時間 | 373 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 104,888 KB |
最終ジャッジ日時 | 2024-09-29 01:37:25 |
合計ジャッジ時間 | 17,996 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
class SegmentTreeBase_:def ope(self, l, r):raise NotImplementedErrordef e(self):raise NotImplementedErrordef __init__(self, n, init=None):self.n = nself.n0 = 1 << (n - 1).bit_length()self.data = [self.e()] * (2 * self.n0)if init is not None:for i in range(n):self.data[self.n0 + i] = init[i]for i in range(self.n0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def build(self):for i in range(self.n0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def set(self, i, x):i += self.n0self.data[i] = xwhile i > 1:i >>= 1self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def get(self, i):return self.data[i + self.n0]def __getitem__(self, i):return self.data[i + self.n0]def __setitem__(self, i, x):self.set(i, x)def prod(self, l, r):assert 0 <= l <= r <= self.n0l += self.n0r += self.n0lles = self.e()rres = self.e()while l < r:if l & 1:lles = self.ope(lles, self.data[l])l += 1if r & 1:r -= 1rres = self.ope(self.data[r], rres)l >>= 1r >>= 1return self.ope(lles, rres)def max_right(self, l, f):if l == self.n:return self.nl += self.n0sm = self.e()while 1:while l % 2 == 0:l >>= 1if not f(self.ope(sm, self.data[l])):while l < self.n0:l <<= 1if f(self.ope(sm, self.data[l])):sm = self.ope(sm, self.data[l])l += 1return l - self.n0sm = self.ope(sm, self.data[l])l += 1if l & -l == l:breakreturn self.ndef min_left(self, r, f):if r == 0:return 0r += self.n0sm = self.e()while 1:r -= 1while r > 1 and r % 2:r >>= 1if not f(self.ope(self.data[r], sm)):while r < self.n0:r = 2 * r + 1if f(self.ope(self.data[r], sm)):sm = self.ope(self.data[r], sm)r -= 1return r + 1 - self.n0sm = self.ope(self.data[r], sm)if r & -r == r:breakreturn 0class RangeSum(SegmentTreeBase_):def ope(self, l, r):return l + rdef e(self):return 0n, m, k = map(int, input().split())S = list(map(int, input().split()))dist = [[1 << 60] * n for _ in range(n)]for i in range(n):dist[i][i] = 0for _ in range(m):a, b, c = map(int, input().split())a -= 1b -= 1dist[a][b] = cdist[b][a] = cfor t in range(n):for i in range(n):for j in range(n):dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j])for i in range(k + 1):S[i] -= 1C = [0] * kfor i in range(k):d = dist[S[i]][S[i + 1]]C[i] = dseg = RangeSum(k, C)Q = int(input())for _ in range(Q):t, x, y = map(int, input().split())if t == 1:y -= 1S[x] = yif x != 0:seg.set(x - 1, dist[S[x - 1]][S[x]])if x != k:seg.set(x, dist[S[x]][S[x + 1]])else:print(seg.prod(x, y))