解説
を偶奇で区別して、ねこを 個の独立した二部グラフに分割すると、シミュレーションがかなり楽になります。
これは、で鳴いているねこは、で必ず鳴いているためです。
を跨いで隣接する鳴いているねこを連結成分とみなします。
各連結成分が高々ずつ延びる様は、主客転倒をして、が一致する連結成分の隣接との間が埋まる様と見なすことで、扱いやすくなります。
そして、整数列を、とが出会うような環とみなすことで、を高速に解く問題に帰着できます。
これは、例えば累積和上の二分探索などにより、で解くことができます。
提出例 (Python)
from bisect import insort
from bisect import bisect_right
from collections import defaultdict
INF=10**18
MOD=998244353
M, D=map(int, input().split())
E=2*D
A1=list(map(int, input().split()))
A1.sort()
A2= sorted(set(b for a in A1 for b in (a-D, a+D)))
def refs(A):
isz=len(A)
prev=[-INF]*E
shifts= []
dcnts= defaultdict(int)
for a in A:
cat=a%E
d=(a-prev[cat])//E - 1
prev[cat]=a
shifts.append(d)
dcnts[d]+=1
shifts.sort()
dtoc={}
psum={}
cnt=0
summ=0
for d, c in sorted(dcnts.items()):
cnt+=c
summ+=d*c
dtoc[d]=cnt
psum[d]=summ
return shifts, dtoc, cnt, isz, psum
S1, M1, C1, I1, P1 = refs(A1)
S2, M2, C2, I2, P2 = refs(A2)
_=int(input())
Bs=list(map(int, input().split()))
for B in Bs:
S3, M3, C3, I3, P3 = (S1, M1, C1, I1, P1) if B%2==0 else (S2, M2, C2, I2, P2)
X=B//2
idx = bisect_right(S3, 2*X) - 1
cleq = 0 if idx < 0 else M3[S3[idx]]
pleq = 0 if idx < 0 else P3[S3[idx]]
summ = I3 + pleq + 2*X*(I3 - cleq)
summ%=MOD
print(summ)
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。