結果
問題 | No.2640 traO Stamps |
ユーザー | chineristAC |
提出日時 | 2024-02-19 23:11:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 690 ms / 2,000 ms |
コード長 | 2,269 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 137,596 KB |
最終ジャッジ日時 | 2024-02-19 23:11:46 |
合計ジャッジ時間 | 19,506 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
56,248 KB |
testcase_01 | AC | 39 ms
56,248 KB |
testcase_02 | AC | 39 ms
56,248 KB |
testcase_03 | AC | 41 ms
58,340 KB |
testcase_04 | AC | 43 ms
58,340 KB |
testcase_05 | AC | 41 ms
58,340 KB |
testcase_06 | AC | 521 ms
123,640 KB |
testcase_07 | AC | 539 ms
127,572 KB |
testcase_08 | AC | 663 ms
134,516 KB |
testcase_09 | AC | 479 ms
117,332 KB |
testcase_10 | AC | 579 ms
131,252 KB |
testcase_11 | AC | 527 ms
117,856 KB |
testcase_12 | AC | 609 ms
134,460 KB |
testcase_13 | AC | 502 ms
118,804 KB |
testcase_14 | AC | 606 ms
133,072 KB |
testcase_15 | AC | 544 ms
121,836 KB |
testcase_16 | AC | 528 ms
129,432 KB |
testcase_17 | AC | 542 ms
130,812 KB |
testcase_18 | AC | 544 ms
121,828 KB |
testcase_19 | AC | 627 ms
133,380 KB |
testcase_20 | AC | 549 ms
133,632 KB |
testcase_21 | AC | 510 ms
122,176 KB |
testcase_22 | AC | 613 ms
135,764 KB |
testcase_23 | AC | 483 ms
118,760 KB |
testcase_24 | AC | 517 ms
118,896 KB |
testcase_25 | AC | 588 ms
134,892 KB |
testcase_26 | AC | 441 ms
125,628 KB |
testcase_27 | AC | 389 ms
125,884 KB |
testcase_28 | AC | 398 ms
125,628 KB |
testcase_29 | AC | 422 ms
127,164 KB |
testcase_30 | AC | 690 ms
137,596 KB |
testcase_31 | AC | 636 ms
137,156 KB |
testcase_32 | AC | 575 ms
130,304 KB |
testcase_33 | AC | 614 ms
131,136 KB |
ソースコード
import sys from itertools import permutations from heapq import heappop,heappush from collections import deque import random import bisect input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) class SegmentTree: 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 self.size = n 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: k >>= 1 self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1]) def query(self, l, r): if r==self.size: r = self.num res = self.ide_ele l += self.num r += self.num right = [] while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: right.append(self.tree[r-1]) l >>= 1 r >>= 1 for e in right[::-1]: res = self.segfunc(res,e) return res INF = 10**17 N,M,K = mi() A = li() edge = [[INF]*N for i in range(N)] for _ in range(M): a,b,c = mi() edge[a-1][b-1] = min(edge[a-1][b-1],c) edge[b-1][a-1] = min(edge[b-1][a-1],c) for i in range(N): edge[i][i] = 0 for k in range(N): for i in range(N): for j in range(N): if edge[i][j] > edge[i][k] + edge[k][j]: edge[i][j] = edge[i][k] + edge[k][j] e = (-1,-1) def merge(x,y): if x == e: return y if y == e: return x c = x[0] + y[0] + edge[x[2]][y[1]] return (c,x[1],y[2]) seg = SegmentTree([(0,A[i]-1,A[i]-1) for i in range(K+1)],merge,e) res = [] for _ in range(int(input())): t,x,y = mi() if t == 1: seg.update(x,(0,y-1,y-1)) continue l,r = x,y #print("l,r",l,r) ans = seg.query(l,r+1)[0] res.append(ans) print(*res,sep="\n")