結果
問題 |
No.3134 二分探索木
|
ユーザー |
|
提出日時 | 2025-05-02 23:16:36 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 755 bytes |
コンパイル時間 | 546 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 106,852 KB |
最終ジャッジ日時 | 2025-05-02 23:16:40 |
合計ジャッジ時間 | 3,421 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 5 |
other | RE * 15 |
ソースコード
N = int(input()) A = list(map(int, input().split())) import sys sys.setrecursionlimit(10**6) from sortedcontainers import SortedList now = SortedList() G = [[-1, -1] for _ in range(N)] now.add((A[0], 0)) def add(i, a): if A[a] < A[i]: if G[i][0] == -1: G[i][0] = a else: add(G[i][0], a) else: if G[i][1] == -1: G[i][1] = a else: add(G[i][1], a) for i in range(1, N): j = now.bisect_left((A[i], i)) if j == 0: j += 1 add(now[j-1][1], i) now.add((A[i], i)) B = [0] * N C = [0] * N def dfs(i, p, d): B[i] = d for j in G[i]: if j != -1: C[i] += dfs(j, i, d+1) return C[i]+1 dfs(0, -1, 0) print(*B) print(*C)