結果

問題 No.1919 Many Monster Battles
ユーザー googol_S0googol_S0
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

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]=0
B.append(siz)
def Badd(B,a,x):
z=a
while z<=B[-1]:
B[z]+=x
z+=(z&(-z))
def Bsum(B,a):
r=0
z=a
while z>0:
r+=B[z]
z-=(z&(-z))
return r
from copy import *
def init(N,node,A,unit,func):
while len(node):
del node[-1]
n=1
while n<N:
n<<=1
for i in range(n*2-1):
if len(node)<=i:
node.append(unit)
else:
node[i]=unit
for 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]+x
node[y-1]+=a
while y>1:
y=y>>1
node[y-1]=node[(y<<1)-1]+node[y<<1]
def query(node,l,r):
x,y=l,r
z=node[-1]-1
rr=node[-2]
rl=node[-2]
while True:
if x==y:
return rl+rr
if x&1:
rl=rl+node[x+z]
x+=1
if y&1:
rr=node[y+z-1]+rr
if z==0:
return rl+rr
x>>=1
y>>=1
z>>=1
mod=10**9+7
def comp(x):
#y=sorted(set(x))
y=sorted(x)
d=dict()
for i in range(len(y)):
d[y[i]]=i
return d
def 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=0
segy=[]
segz=[]
Binit(segy,N+3)
Binit(segz,N+3)
c=0
for i in range(N):
if i and X[i]==X[i-1]:
c+=1
else:
c=0
a,b=y[Y[i]],z[Z[i]]
ANS=(ANS+X[i][0]*(Bsum(segy,a)+Bsum(segz,b)-i+c))%mod
Badd(segy,a+1,1)
Badd(segz,b+1,1)
Binit(segy,N+3)
Binit(segz,N+3)
c=0
for i in range(N-1,-1,-1):
if i+1<N and X[i]==X[i+1]:
c+=1
else:
c=0
a,b=y[Y[i]],z[Z[i]]
ANS=(ANS-X[i][0]*(-Bsum(segy,a+1)-Bsum(segz,b+1)+(N-1-i)+c))%mod
Badd(segy,a+1,1)
Badd(segz,b+1,1)
return ANS
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if 0:
N=200000
from 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0