test/yosupo/cartesian_tree.test.cpp

View this file on GitHub
Last update: 2024-01-07 23:25:49+09:00
Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

Cartesian Tree (tree/cartesian_tree.hpp)

Code

#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");
}