結果
問題 | No.1919 Many Monster Battles |
ユーザー |
![]() |
提出日時 | 2022-04-29 23:16:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,297 ms / 2,000 ms |
コード長 | 2,229 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 205,456 KB |
最終ジャッジ日時 | 2024-06-29 05:01:28 |
合計ジャッジ時間 | 23,931 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
def Binit(B,siz):while len(B)<siz+1:B.append(0)while len(B)>siz+1:del B[-1]for i in range(siz+1):B[i]=0B.append(siz)def Badd(B,a,x):z=awhile z<=B[-1]:B[z]+=xz+=(z&(-z))def Bsum(B,a):r=0z=awhile z>0:r+=B[z]z-=(z&(-z))return rfrom copy import *def init(N,node,A,unit,func):while len(node):del node[-1]n=1while n<N:n<<=1for i in range(n*2-1):if len(node)<=i:node.append(unit)else:node[i]=unitfor i in range(len(A)):node[n-1+i]=A[i]for i in range(n-2,-1,-1):node[i]=node[(i<<1)+1]+node[(i<<1)+2]node.append(func)node.append(unit)node.append(n)def upd(node,x,a):y=node[-1]+xnode[y-1]+=awhile y>1:y=y>>1node[y-1]=node[(y<<1)-1]+node[y<<1]def query(node,l,r):x,y=l,rz=node[-1]-1rr=node[-2]rl=node[-2]while True:if x==y:return rl+rrif x&1:rl=rl+node[x+z]x+=1if y&1:rr=node[y+z-1]+rrif z==0:return rl+rrx>>=1y>>=1z>>=1mod=10**9+7def comp(x):#y=sorted(set(x))y=sorted(x)d=dict()for i in range(len(y)):d[y[i]]=ireturn ddef solve(A,B):N=len(A)X=[(A[i]<<31)+B[i] for i in range(N)]X.sort()X=[(X[i]>>31,X[i]&((1<<31)-1)) for i in range(N)]Y=[X[i][0]-X[i][1] for i in range(N)]Z=[X[i][0]+X[i][1] for i in range(N)]y,z=comp(Y),comp(Z)ANS=0segy=[]segz=[]Binit(segy,N+3)Binit(segz,N+3)c=0for i in range(N):if i and X[i]==X[i-1]:c+=1else:c=0a,b=y[Y[i]],z[Z[i]]ANS=(ANS+X[i][0]*(Bsum(segy,a)+Bsum(segz,b)-i+c))%modBadd(segy,a+1,1)Badd(segz,b+1,1)Binit(segy,N+3)Binit(segz,N+3)c=0for i in range(N-1,-1,-1):if i+1<N and X[i]==X[i+1]:c+=1else:c=0a,b=y[Y[i]],z[Z[i]]ANS=(ANS-X[i][0]*(-Bsum(segy,a+1)-Bsum(segz,b+1)+(N-1-i)+c))%modBadd(segy,a+1,1)Badd(segz,b+1,1)return ANSN=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))if 0:N=200000from random import *A=[randrange(0,1000000000) for i in range(N)]B=[randraange(0,1000000000) for i in range(N)]print(solve(A,B)*2%mod,solve(B,A)*2%mod)