結果
問題 | No.3134 二分探索木 |
ユーザー |
![]() |
提出日時 | 2025-05-02 21:37:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 1,121 bytes |
コンパイル時間 | 4,179 ms |
コンパイル使用メモリ | 256,620 KB |
実行使用メモリ | 35,496 KB |
最終ジャッジ日時 | 2025-05-02 21:37:52 |
合計ジャッジ時間 | 6,733 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 15 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 4000000000000000001LL pair<int,int> op(pair<int,int> a,pair<int,int> b){ return min(a,b); } pair<int,int> e(){ return {Inf32,Inf32}; } segtree<pair<int,int>,op,e> seg; int root = -1; vector<vector<int>> E; void dfs(int l,int r,int pp){ if(l==r)return; auto p = seg.prod(l,r); if(pp!=-1){ E[pp].push_back(p.first); } else root = p.first; dfs(l,p.second,p.first); dfs(p.second+1,r,p.first); } int B[200005],C[200005]; void dfs2(int v,int p,int d){ B[v] = d; rep(i,E[v].size()){ int u = E[v][i]; if(u==p)continue; dfs2(u,v,d+1); C[v] += C[u]+1; } } int main(){ int n; cin>>n; seg = segtree<pair<int,int>,op,e>(n); rep(i,n){ int a; cin>>a; a--; seg.set(a,pair<int,int>(i,a)); } E.resize(n); dfs(0,n,-1); dfs2(root,-1,0); rep(i,n){ if(i!=0)cout<<' '; cout<<B[i]; }cout<<endl; rep(i,n){ if(i!=0)cout<<' '; cout<<C[i]; }cout<<endl; return 0; }