結果

問題 No.2640 traO Stamps
ユーザー timi
提出日時 2024-02-19 22:16:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 802 ms / 2,000 ms
コード長 2,949 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 105,248 KB
最終ジャッジ日時 2024-09-29 02:12:14
合計ジャッジ時間 21,949 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N,M,K=map(int, input().split())
S=list(map(int, input().split()))
def warshall_floyd(d):
#d[i][j]: ij
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j],d[i][k] + d[k][j])
return d
##############################
n,w =N,M
d = [[float("inf")]*n for i in range(n)]
#d[u][v] : uv(inf)
for i in range(w):
x,y,z = map(int,input().split())
x-=1;y-=1
d[x][y] = z;d[y][x] = z
for i in range(n):
d[i][i] = 0 #
B=(warshall_floyd(d))
#####segfunc#####
def segfunc(x, y):
return x+y
#################
#####ide_ele#####
ide_ele = 0
#################
class SegTree:
"""
init(init_val, ide_ele): init_val O(N)
update(k, x): kx O(N)
query(l, r): [l, r)segfunc O(logN)
"""
def __init__(self, init_val, segfunc, ide_ele):
"""
init_val:
segfunc:
ide_ele:
n:
num: n2
tree: (1-index)
"""
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):
"""
kx
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
A=[]
for i in range(K):
p,q=S[i],S[i+1]
A.append(B[p-1][q-1])
seg = SegTree(A, segfunc, ide_ele)
Q=int(input())
for i in range(Q):
t,x,y=map(int, input().split())
if t==1:
p,q=x-1,x
if x-1>=0:
l=S[x-1]-1
d=B[l][y-1]
seg.update(x-1,d)
if x+1<=K:
r=S[x+1]-1
d=B[r][y-1]
seg.update(x,d)
S[x]=y
else:
print(seg.query(x,y))
# print(seg.query(0, 8))
# seg.update(5, 0)
# print(seg.query(0, 8))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0