結果

問題 No.3134 二分探索木
ユーザー flippergo
提出日時 2025-07-05 12:45:30
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,394 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 403,800 KB
最終ジャッジ日時 2025-07-29 01:58:58
合計ジャッジ時間 14,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 14 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int,input().split()))
k = 0
while 2**k<N:
    k += 1
M = 2**k
T1 = [0]*(M+1)
T2 = [[0,0] for _ in range(N+1)]
def update(x):
    while x<=M:
        T1[x] += 1
        x += x&(-x)
def cumsum(x):
    tot = 0
    while x>0:
        tot += T1[x]
        x -= x&(-x)
    return tot
update(A[0])
for i in range(1,N):
    x = A[i]
    cuml = cumsum(x)
    high = x
    low = -1
    while high-low>1:
        mid = (high+low)//2
        if cumsum(mid)>=cuml:
            high = mid
        else:
            low = mid
    left = high
    high = N+1
    low = x
    while high-low>1:
        mid = (high+low)//2
        if cumsum(mid)>cuml:
            high = mid
        else:
            low =mid
    right = high
    if left==0:
        T2[right][0] = x
    elif right==N+1:
        T2[left][1] = x
    else:
        if T2[left][1]==0:
            T2[left][1] = x
        else:
            T2[right][0] = x
    update(x)
B = [0]*(N+1)
C = [[0,0] for _ in range(N+1)]
def dfs(x,p):
    global cnt
    B[x] = B[p]+1
    C[x][0] = cnt
    cnt += 1
    for y in T2[x]:
        if y==0:continue
        dfs(y,x)
    C[x][1] = cnt
    cnt += 1
cnt = 0
B[0] = -1
dfs(A[0],0)
C = [(C[i][1]-C[i][0])//2 for i in range(N+1)]
ans1 = [0]*N
ans2 = [0]*N
for i in range(N):
    ans1[i] = B[A[i]]
    ans2[i] = C[A[i]]
print(*ans1)
print(*ans2)
0