結果
問題 | No.3134 二分探索木 |
ユーザー |
|
提出日時 | 2025-05-02 23:12:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 1,064 bytes |
コンパイル時間 | 2,265 ms |
コンパイル使用メモリ | 199,900 KB |
実行使用メモリ | 37,180 KB |
最終ジャッジ日時 | 2025-05-02 23:12:55 |
合計ジャッジ時間 | 4,853 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 15 |
ソースコード
#include <atcoder/segtree> #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (int)(n); i++) const ll INF = 1e18; using S = ll; S op(S l, S r) { return min(l, r); } S e() { return INF; } void solve() { ll n; cin >> n; vector<ll> a(n), b(n, 0), c(n, 0); atcoder::segtree<S, op, e> seg(n); rep(i, n) { cin >> a[i], a[i]--; seg.set(a[i], i); } auto dfs = [&](auto self, ll i, ll l, ll r, ll d) -> void { b[i] = d; rep(t, 2) { ll nl, nr; if (t == 0) { nl = l, nr = a[i]; } else { nl = a[i] + 1, nr = r; } ll j = seg.prod(nl, nr); if (j < INF) { self(self, j, nl, nr, d + 1); c[i] += c[j] + 1; } } }; dfs(dfs, 0, 0, n, 0); rep(i, n) cout << (i ? " " : "") << b[i]; cout << '\n'; rep(i, n) cout << (i ? " " : "") << c[i]; cout << '\n'; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int T = 1; for (int t = 0; t < T; t++) { solve(); } return 0; }