結果

問題 No.3134 二分探索木
コンテスト
ユーザー moon17
提出日時 2025-05-02 22:16:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 568 bytes
コンパイル時間 653 ms
コンパイル使用メモリ 82,960 KB
実行使用メモリ 127,148 KB
最終ジャッジ日時 2025-05-02 22:16:25
合計ジャッジ時間 4,024 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 3 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,*a=map(int,open(0).read().split())
a=[i-1 for i in a]
b,c=[0]*n,[1]*n
l,r=[-1]*n,[-1]*n
g=[[]for _ in range(n)]
for i in range(1,n):
  p=a[0]
  now=a[i]
  for j in range(20):
    if now<p:
      if l[p]==-1:
        l[p]=now
        g[p]+=now,
        b[i]=j+1
        break
      p=l[p]
    else:
      if r[p]==-1:
        r[p]=now
        g[p]+=now,
        b[i]=j+1
        break
      p=r[p]
q=[(a[0],-1,0)]
while q:
  p,z,s=q.pop()
  if s:
    c[z]+=c[p]
    continue
  for v in g[p]:
    if v!=z:
      q+=(v,p,1),(v,p,0),
print(*b)
print(*[c[i]-1for i in a])
0