結果
問題 | No.3134 二分探索木 |
ユーザー |
![]() |
提出日時 | 2025-05-02 21:44:11 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 865 ms / 2,000 ms |
コード長 | 1,642 bytes |
コンパイル時間 | 2,666 ms |
コンパイル使用メモリ | 81,668 KB |
実行使用メモリ | 90,236 KB |
最終ジャッジ日時 | 2025-05-02 21:44:24 |
合計ジャッジ時間 | 10,889 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 15 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.TreeSet; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(sa[i]) - 1; } br.close(); Node[] arr = new Node[n]; int[] ai = new int[n]; for (int i = 0; i < n; i++) { Node o = new Node(); o.i = i; arr[i] = o; ai[a[i]] = i; } TreeSet<Integer> set = new TreeSet<>(); for (int i = 0; i < n; i++) { set.add(a[i]); Integer r = set.higher(a[i]); if (r != null) { Node o = arr[ai[r]]; if (o.l == null) { o.l = arr[ai[a[i]]]; continue; } } Integer l = set.lower(a[i]); if (l != null) { Node o = arr[ai[l]]; if (o.r == null) { o.r = arr[ai[a[i]]]; continue; } } } dfs(arr[0], 0); StringBuilder sb = new StringBuilder(); for (Node o : arr) { sb.append(o.dep).append(' '); } sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); sb = new StringBuilder(); for (Node o : arr) { sb.append(o.size).append(' '); } sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); } static int dfs(Node o, int dep) { o.dep = dep; int size = 1; if (o.l != null) { size += dfs(o.l, dep + 1); } if (o.r != null) { size += dfs(o.r, dep + 1); } o.size = size - 1; return size; } static class Node { int i, dep, size; Node l, r; } }