This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
#include "../../template/template.hpp"
#include "../../graph/others/cartesian-tree.hpp"
int main() {
int N;
cin >> N;
vector< int > A(N);
for(auto &a : A) cin >> a;
auto p = cartesian_tree(A);
for(int i = 0; i < N; i++) {
if(p[i] >= 0) cout << p[i] << " ";
else cout << i << " ";
}
cout << "\n";
}
#line 1 "test/verify/yosupo-cartesian-tree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
#line 1 "template/template.hpp"
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
using namespace std;
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template <typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for (auto &e : t) fill_v(e, v);
}
template <typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(std::forward<F>(f)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <typename F>
inline decltype(auto) MFP(F &&f) {
return FixPoint<F>{std::forward<F>(f)};
}
#line 4 "test/verify/yosupo-cartesian-tree.test.cpp"
#line 2 "graph/others/cartesian-tree.hpp"
/**
* @brief Cartesian Tree
*
* @see https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/
*/
template <typename T>
vector<int> cartesian_tree(const vector<T> &v) {
int n = (int)v.size();
vector<int> par(n, -1);
stack<int> st;
for (int i = 0; i < n; i++) {
int last = -1;
while (!st.empty() && v[st.top()] >= v[i]) {
last = st.top();
st.pop();
}
if (!st.empty()) par[i] = st.top();
if (last >= 0) par[last] = i;
st.emplace(i);
}
return par;
}
#line 6 "test/verify/yosupo-cartesian-tree.test.cpp"
int main() {
int N;
cin >> N;
vector< int > A(N);
for(auto &a : A) cin >> a;
auto p = cartesian_tree(A);
for(int i = 0; i < N; i++) {
if(p[i] >= 0) cout << p[i] << " ";
else cout << i << " ";
}
cout << "\n";
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | almost-decreasing_00 | AC | 113 ms | 11 MB |
g++ | almost-decreasing_01 | AC | 55 ms | 7 MB |
g++ | almost-increasing_00 | AC | 123 ms | 15 MB |
g++ | almost-increasing_01 | AC | 61 ms | 9 MB |
g++ | decreasing_00 | AC | 121 ms | 11 MB |
g++ | decreasing_01 | AC | 60 ms | 7 MB |
g++ | example_00 | AC | 6 ms | 3 MB |
g++ | example_01 | AC | 5 ms | 3 MB |
g++ | increasing_00 | AC | 122 ms | 15 MB |
g++ | increasing_01 | AC | 83 ms | 9 MB |
g++ | random_00 | AC | 128 ms | 11 MB |
g++ | random_01 | AC | 63 ms | 7 MB |
g++ | random_02 | AC | 75 ms | 8 MB |
g++ | random_03 | AC | 60 ms | 7 MB |
g++ | random_04 | AC | 107 ms | 10 MB |
g++ | small_00 | AC | 5 ms | 3 MB |
g++ | small_01 | AC | 5 ms | 3 MB |
g++ | small_02 | AC | 5 ms | 3 MB |
g++ | small_03 | AC | 5 ms | 3 MB |
g++ | small_04 | AC | 5 ms | 3 MB |
g++ | small_05 | AC | 5 ms | 3 MB |
g++ | small_06 | AC | 5 ms | 3 MB |
g++ | small_07 | AC | 5 ms | 3 MB |
g++ | small_08 | AC | 5 ms | 3 MB |
g++ | small_09 | AC | 5 ms | 3 MB |
clang++ | almost-decreasing_00 | AC | 111 ms | 11 MB |
clang++ | almost-decreasing_01 | AC | 56 ms | 7 MB |
clang++ | almost-increasing_00 | AC | 118 ms | 15 MB |
clang++ | almost-increasing_01 | AC | 62 ms | 9 MB |
clang++ | decreasing_00 | AC | 111 ms | 11 MB |
clang++ | decreasing_01 | AC | 57 ms | 7 MB |
clang++ | example_00 | AC | 5 ms | 3 MB |
clang++ | example_01 | AC | 5 ms | 3 MB |
clang++ | increasing_00 | AC | 113 ms | 15 MB |
clang++ | increasing_01 | AC | 56 ms | 9 MB |
clang++ | random_00 | AC | 120 ms | 11 MB |
clang++ | random_01 | AC | 59 ms | 7 MB |
clang++ | random_02 | AC | 71 ms | 8 MB |
clang++ | random_03 | AC | 60 ms | 7 MB |
clang++ | random_04 | AC | 98 ms | 10 MB |
clang++ | small_00 | AC | 5 ms | 3 MB |
clang++ | small_01 | AC | 5 ms | 3 MB |
clang++ | small_02 | AC | 5 ms | 3 MB |
clang++ | small_03 | AC | 5 ms | 3 MB |
clang++ | small_04 | AC | 5 ms | 3 MB |
clang++ | small_05 | AC | 5 ms | 3 MB |
clang++ | small_06 | AC | 5 ms | 3 MB |
clang++ | small_07 | AC | 5 ms | 3 MB |
clang++ | small_08 | AC | 5 ms | 3 MB |
clang++ | small_09 | AC | 5 ms | 3 MB |