結果

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

ソースコード

diff # 

n = int(input())
A = list(map(int, input().split()))
lst = [[-1, -1, -1] for _ in range(n)]
id = 0

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

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

from bisect import *

for i in range(1, n):
    a = A[i]
    ind = bisect(O, a)
    c0 = (-1, -1)
    c1 = (-1, -1)
    if 0 <= ind-1 < len(O):
        a0 = O[ind-1]
        c0 = F[a0]
    if 0 <= ind < len(O):
        a1 = O[ind]
        c1 = F[a1]
    if c0[0] < c1[0]:
        now = c1[1]
        le = c1[0]
    else:
        now = c0[1]
        le = c0[0]
    pa, l, r = lst[now]
    if pa < a:
        N[D[pa]].append(i)
        R[i].append(D[pa])
        lst[now][2] = id
        lst[id][0] = a
        id += 1
        insort(O, a)
    else:
        N[D[pa]].append(i)
        R[i].append(D[pa])
        lst[now][1] = id
        lst[id][0] = a
        id += 1
    insort(O, a)
    F[a] = (le + 1, id-1)

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