結果
問題 | No.2640 traO Stamps |
ユーザー |
|
提出日時 | 2024-02-19 21:36:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 332 ms / 2,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 110,312 KB |
最終ジャッジ日時 | 2024-09-29 01:31:45 |
合計ジャッジ時間 | 10,996 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
class BinaryIndexedTree():def __init__(self,default=0):self.size=0if type(default)==int:self.size=defaultelse:self.size=len(default)self.bit=[0 for i in range(self.size+1)]self.stan=[0 for i in range(self.size)]if type(default)!=int:for i,j in enumerate(default):self[i]=jdef __setitem__(self,pos,val):add=val-self.stan[pos]self.stan[pos]=valpos+=1while pos<=self.size:self.bit[pos]+=addpos+=pos&(-pos)def __getitem__(self,pos):if type(pos)==int:return self.stan[pos]else:left=pos.startif left==None:left=0right=pos.stopif right==None:right=self.sizereturn self._sum0(right-1)-self._sum0(left-1)def _sum0(self,right):pos=right+1ret=0while pos>0:ret+=self.bit[pos]pos-=pos&(-pos)return retimport sys#sys.setrecursionlimit((1<<19)-1)#import pypyjit#pypyjit.set_param('max_unroll_recursion=-1')input=sys.stdin.buffer.readlineINF=1<<60N,M,K=map(int,input().split())K+=2S=list(map(int,input().split()))+[1]di=[[INF]*N for i in range(N)]for i in range(N):di[i][i]=0for i in range(M):A,B,C=map(int,input().split())di[A-1][B-1]=Cdi[B-1][A-1]=Cfor i in range(N):for j in range(N):for k in range(N):di[j][k]=min(di[j][k],di[j][i]+di[i][k])st=[0]*KS[0]-=1for i in range(K-1):S[i+1]-=1st[i+1]=di[S[i]][S[i+1]]bit=BinaryIndexedTree(st)Q=int(input())for i in range(Q):T,X,Y=map(int,input().split())if T==1:Y-=1S[X]=Yif X!=0:bit[X]=di[S[X-1]][Y]bit[X+1]=di[Y][S[X+1]]else:print(bit[X+1:Y+1])