外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

U - Nyan Nyan Nyan Nyan Infinite Maigai

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529

配点 550 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

BiB_iを偶奇で区別して、ねこをDD 個の独立した二部グラフに分割すると、シミュレーションがかなり楽になります。

これは、T=mT=mで鳴いているねこは、T=m+2T=m+2で必ず鳴いているためです。

2D2Dを跨いで隣接する鳴いているねこを連結成分とみなします。

各連結成分が高々22ずつ延びる様は、主客転倒をして、mod  2D\mod 2Dが一致する連結成分の隣接との間が埋まる様と見なすことで、扱いやすくなります。

そして、整数列を、∞\inftyと−∞-\inftyが出会うような環とみなすことで、f(t)=∑imin⁡(xi,2t)f(t)=\sum_{i}^{} \min(x_i, 2t)を高速に解く問題に帰着できます。

これは、例えば累積和上の二分探索などにより、O((M+Q)log⁡(M+Q))O((M+Q)\log(M+Q))で解くことができます。

提出例 (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)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。