結果

問題 No.1170 Never Want to Walk
ユーザー ああ
提出日時 2025-10-14 01:57:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,891 ms / 2,000 ms
コード長 1,207 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 291,788 KB
最終ジャッジ日時 2025-10-14 01:58:22
合計ジャッジ時間 26,106 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def aa(m):
  while m>1:
    m//=2
    seg[m]=(min(seg[m*2][0],seg[m*2+1][0]),max(seg[m*2+1][1],seg[m*2+1][1]))

    
def bb(l,r):
  q,w=1<<60,0
  while l<r:
    if l&1:
      q=min(seg[l][0],q)
      w=max(seg[l][1],w)
      l+=1
    if r&1:
      r-=1
      q=min(seg[r][0],q)
      w=max(seg[r][1],w)
    l//=2;r//=2
  return (q,w)

n,a,b=map(int,input().split())
x=list(map(int,input().split()))
s=set()
for i in x:
  s.add(i+a);s.add(i-a);s.add(i+b);s.add(i-b);s.add(i)
y={}
for i,j in enumerate(sorted(list(s))):
  y[j]=i
v=1<<len(s).bit_length()
seg=[(1<<60,0) for i in range(v*2)]
ans=[0]*n;z={}
for i in range(n):
  z[x[i]]=i
  seg[y[x[i]]+v]=[x[i],x[i]];aa(y[x[i]]+v)
k=[0]*n
for i in range(n):
  c=y[x[i]]
  if seg[c+v][0]==1<<60:
    continue
  f=deque([x[i]]);s=1
  seg[c+v]=(1<<60,0);aa(c+v)
  while f:
    A=f.pop()
    k[z[A]]=i
    while 1:
      q,w=bb(y[A-b]+v,y[A-a]+1+v)
      if q==1<<60:
        break
      s+=1
      f.append(q);seg[v+y[q]]=(1<<60,0);aa(v+y[q])
    while 1:
      q,w=bb(y[A+a]+v,y[A+b]+1+v)
      if q==1<<60:
        break
      s+=1
      f.append(q);seg[v+y[q]]=(1<<60,0);aa(v+y[q])
  ans[i]=s
for i in range(n):
  print(ans[k[i]])
0