結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

int main()
{
    int64_t n;
    cin >> n;
    vector<int64_t> as(n);
    for (auto &&a : as)
    {
        cin >> a;
        a--;
    }

    vector<pair<int64_t, int64_t>> lrs(n, {-1, -1});

    for (int64_t i = 1; i < n; i++)
    {
        int64_t look = 0;

        while (true)
        {
            if (as[i] < as[look])
            {
                if (lrs[look].first == -1)
                {
                    lrs[look].first = i;
                    break;
                }
                else
                {
                    look = lrs[look].first;
                    continue;
                }
            }
            else if (as[look] < as[i])
            {
                if (lrs[look].second == -1)
                {
                    lrs[look].second = i;
                    break;
                }
                else
                {
                    look = lrs[look].second;
                    continue;
                }
            }
        }
    }

    vector<int64_t> bs(n), cs(n);

    auto dfs = [&](auto &&f, int64_t cur, int64_t depth = 0) -> int64_t
    {
        bs[cur] = depth;

        if (lrs[cur].first != -1)
        {
            cs[cur] += f(f, lrs[cur].first, depth + 1);
        }

        if (lrs[cur].second != -1)
        {
            cs[cur] += f(f, lrs[cur].second, depth + 1);
        }

        return cs[cur] + 1;
    };

    dfs(dfs, 0);

    for (auto &&b : bs)
    {
        cout << b << ' ';
    }
    cout << endl;
    for (auto &&c : cs)
    {
        cout << c << ' ';
    }
    cout << endl;

    return 0;
}
0