sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree" #include "../../tree/cartesian_tree.hpp" #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> a(N); for (auto& x : a) cin >> x; auto p = cartesian_tree(a); for (int i = 0; i < N; ++i) cout << (p[i] == -1 ? i : p[i]) << (i < N - 1 ? " " : "\n"); }
#line 1 "test/yosupo/cartesian_tree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree" #line 2 "tree/cartesian_tree.hpp" #include <stack> #include <vector> template <typename T> std::vector<int> cartesian_tree(const std::vector<T>& a) { const int n = a.size(); std::vector<int> par(n, -1); std::stack<int> st; for (int i = 0; i < n; ++i) { int j = -1; while (!st.empty() && a[st.top()] >= a[i]) { j = st.top(); st.pop(); } if (!st.empty()) par[i] = st.top(); if (j != -1) par[j] = i; st.push(i); } return par; } #line 4 "test/yosupo/cartesian_tree.test.cpp" #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> a(N); for (auto& x : a) cin >> x; auto p = cartesian_tree(a); for (int i = 0; i < N; ++i) cout << (p[i] == -1 ? i : p[i]) << (i < N - 1 ? " " : "\n"); }