test/library-checker/cartesian_tree.test.cpp

• View this file on GitHub
• Last update: 2023-03-05 19:05:08+09:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian Tree (datastructure/cartesian_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"

#include "datastructure/cartesian_tree.hpp"

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    std::vector<int> p = cartesian_tree(a);
    for (int i = 0; i < n; i++) std::cout << p[i] << " \n"[i == n - 1];
}

#line 1 "test/library-checker/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"

#line 2 "datastructure/cartesian_tree.hpp"
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
    int n = int(a.size());
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::stack<int> st;
    for (int i = 0; i < n; i++) {
        std::optional<int> pre = std::nullopt;
        while (!st.empty() && a[i] < a[st.top()]) {
            pre = st.top();
            st.pop();
        }
        if (pre) p[pre.value()] = i;
        if (!st.empty()) p[i] = st.top();
        st.push(i);
    }
    return p;
}
#line 4 "test/library-checker/cartesian_tree.test.cpp"

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    std::vector<int> p = cartesian_tree(a);
    for (int i = 0; i < n; i++) std::cout << p[i] << " \n"[i == n - 1];
}

Back to top page