test/verify/yosupo-cartesian-tree.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 11:04:56+00:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian Tree (graph/others/cartesian-tree.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
// clang-format on

#include <iostream>
#include <vector>

#include "../../graph/others/cartesian-tree.hpp"

using namespace std;

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"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
// clang-format on

#include <iostream>
#include <vector>

#line 2 "graph/others/cartesian-tree.hpp"

#include <stack>
#line 5 "graph/others/cartesian-tree.hpp"

/**
 * @brief Cartesian Tree
 */
template <typename T>
std::vector<int> cartesian_tree(const std::vector<T>& v) {
  int n = (int)v.size();
  std::vector<int> par(n, -1);
  std::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 9 "test/verify/yosupo-cartesian-tree.test.cpp"

using namespace std;

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

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost-decreasing_00	AC	350 ms	11 MB
g++	almost-decreasing_01	AC	160 ms	7 MB
g++	almost-increasing_00	AC	347 ms	15 MB
g++	almost-increasing_01	AC	161 ms	9 MB
g++	decreasing_00	AC	352 ms	11 MB
g++	decreasing_01	AC	160 ms	7 MB
g++	example_00	AC	2 ms	3 MB
g++	example_01	AC	2 ms	4 MB
g++	increasing_00	AC	368 ms	15 MB
g++	increasing_01	AC	172 ms	9 MB
g++	random_00	AC	357 ms	11 MB
g++	random_01	AC	164 ms	7 MB
g++	random_02	AC	204 ms	8 MB
g++	random_03	AC	152 ms	7 MB
g++	random_04	AC	301 ms	9 MB
g++	small_00	AC	2 ms	3 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	3 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	3 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	3 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	3 MB
clang++	almost-decreasing_00	AC	343 ms	11 MB
clang++	almost-decreasing_01	AC	171 ms	7 MB
clang++	almost-increasing_00	AC	351 ms	15 MB
clang++	almost-increasing_01	AC	161 ms	9 MB
clang++	decreasing_00	AC	377 ms	11 MB
clang++	decreasing_01	AC	159 ms	7 MB
clang++	example_00	AC	3 ms	4 MB
clang++	example_01	AC	2 ms	4 MB
clang++	increasing_00	AC	367 ms	15 MB
clang++	increasing_01	AC	161 ms	9 MB
clang++	random_00	AC	370 ms	11 MB
clang++	random_01	AC	175 ms	7 MB
clang++	random_02	AC	204 ms	8 MB
clang++	random_03	AC	153 ms	7 MB
clang++	random_04	AC	288 ms	10 MB
clang++	small_00	AC	2 ms	4 MB
clang++	small_01	AC	2 ms	4 MB
clang++	small_02	AC	2 ms	4 MB
clang++	small_03	AC	2 ms	4 MB
clang++	small_04	AC	2 ms	4 MB
clang++	small_05	AC	2 ms	4 MB
clang++	small_06	AC	2 ms	4 MB
clang++	small_07	AC	2 ms	4 MB
clang++	small_08	AC	2 ms	4 MB
clang++	small_09	AC	2 ms	4 MB

Back to top page