結果

問題 No.3134 二分探索木
ユーザー kidodesu
提出日時 2025-05-02 21:42:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,091 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 148,236 KB
最終ジャッジ日時 2025-05-02 21:42:46
合計ジャッジ時間 5,713 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = list(map(int, input().split()))
lst = []
id = 0

N = [[] for _ in range(n)]
R = [[] for _ in range(n)]

lst.append([A[0], -1, -1])
id = 1
D = {A[i]: i for i in range(n)}

for i in range(1, n):
    now = 0
    while True:
        a, l, r = lst[now]
        if a < A[i]:
            if r == -1:
                N[D[a]].append(i)
                R[i].append(D[a])
                lst[now][2] = id
                lst.append([A[i], -1, -1])
                id += 1
                break
            else:
                now = r
        else:
            if l == -1:
                N[D[a]].append(i)
                R[i].append(D[a])
                lst[now][1] = id
                lst.append([A[i], -1, -1])
                id += 1
                break
            else:
                now = l

B = [0] * n
C = [1] * n
S = [0]
E = []
while S:
    now = S.pop()
    E.append(now)
    for nxt in N[now]:
        B[nxt] = B[now] + 1
        S.append(nxt)

for e in E[::-1]:
    for nxt in R[e]:
        C[nxt] += C[e]

for i in range(n):
    C[i] -= 1

print(*B)
print(*C)
0