結果

問題 No.3134 二分探索木
コンテスト
ユーザー sai
提出日時 2025-05-02 21:40:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,109 bytes
コンパイル時間 3,414 ms
コンパイル使用メモリ 276,820 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2025-05-02 21:40:25
合計ジャッジ時間 7,631 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<int> A(n);
  for (int i = 0; i < n; i++) {
    std::cin >> A[i];
  }
  std::vector<int> B(n), L(n, -1), R(n, -1);
  B[0] = 0;
  for (int i = 1; i < n; i++) {
    int root = 0;
    for (;;) {
      if (A[i] < A[root]) {
        if (L[root] == -1) {
          L[root] = i;
          B[i] = B[root] + 1;
          break;
        } else {
          root = L[root];
        }
      } else {
        if (R[root] == -1) {
          R[root] = i;
          B[i] = B[root] + 1;
          break;
        } else {
          root = R[root];
        }
      }
    }
  }
  std::vector<int> C(n, 0);
  auto dfs = [&](auto self, int v) -> void {
    if (L[v] != -1) {
      self(self, L[v]);
      C[v] += C[L[v]] + 1;
    }
    if (R[v] != -1) {
      self(self, R[v]);
      C[v] += C[R[v]] + 1;
    }
  };
  dfs(dfs, 0);
  for (int i = 0; i < n; i++) {
    std::cout << B[i] << " \n"[i + 1 == n];
  }
  for (int i = 0; i < n; i++) {
    std::cout << C[i] << " \n"[i + 1 == n];
  }
}
0