結果

問題 No.1170 Never Want to Walk
ユーザー ああ
提出日時 2025-10-14 01:53:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,221 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 401,900 KB
最終ジャッジ日時 2025-10-14 01:53:50
合計ジャッジ時間 32,915 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def aa(m):
  while m>1:
    m//=2
    seg[m][0]=min(seg[m*2][0],seg[m*2+1][0])
    seg[m][1]=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