This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../datastructure/cartesiantree.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; int n; cin>>n; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto ps=cartesian_tree(as); for(int i=0;i<n;i++){ if(i) cout<<' '; cout<<(ps[i]<0?i:ps[i]); } cout<<newl; return 0; }
#line 1 "test/yosupo/cartesian_tree.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "datastructure/cartesiantree.cpp" #line 3 "datastructure/cartesiantree.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> vector<int> cartesian_tree(const vector<T> &vs){ int n=vs.size(); vector<int> ps(n,-1),ls(n,-1),rs(n,-1); int cur=0; for(int i=1;i<n;i++){ if(vs[cur]<=vs[i]){ rs[cur]=i; ps[i]=cur; cur=i; continue; } while(~ps[cur] and vs[i]<vs[ps[cur]]) cur=ps[cur]; ps[i]=ps[cur]; if(~ps[i]) rs[ps[i]]=i; ls[i]=cur; ps[cur]=i; cur=i; } return ps; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/yosupo/cartesian_tree.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; int n; cin>>n; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto ps=cartesian_tree(as); for(int i=0;i<n;i++){ if(i) cout<<' '; cout<<(ps[i]<0?i:ps[i]); } cout<<newl; return 0; }