verify/cartesian_tree.test.cpp

View this file on GitHub · Last update: 2026-07-25 04:01:54-07:00

Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• cartesian_tree.hpp
• reverse_comparator.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree

#include <bits/stdc++.h>
#include <cassert>

#include "cartesian_tree.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N; std::cin >> N;
	std::vector<int> A(N); for (auto& a : A) std::cin >> a;

	auto ct = CartesianTree::build_min_tree(A);
	for (int i = 0; i < N; i++) {
		int p = ct[2*i+1].p;
		if (p == -1) {
			p = i;
		} else {
			assert(p & 1);
			p /= 2;
		}
		std::cout << p << " \n"[i+1==N];
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/cartesian_tree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree

#line 5 "verify/cartesian_tree.test.cpp"

#line 2 "src/cartesian_tree.hpp"

#line 5 "src/cartesian_tree.hpp"

#line 2 "src/reverse_comparator.hpp"

#line 5 "src/reverse_comparator.hpp"

template <typename F> struct reverse_comparator_t {
	F f;
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) & {
		return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const& {
		return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) && {
		return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
	template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const&& {
		return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
	}
};

template <typename F> constexpr reverse_comparator_t<std::decay_t<F>> reverse_comparator(F&& f) {
	return { std::forward<F>(f) };
}
#line 7 "src/cartesian_tree.hpp"

class CartesianTree {
public:
	struct Node {
		int l, m, r; // inclusive ranges
		std::array<int, 2> c;
		int p;
	};
	std::vector<Node> nodes;
	int root = -1;

	CartesianTree() {}

	Node& operator [] (int idx) { return nodes[idx]; }
	const Node& operator [] (int idx) const { return nodes[idx]; }

	int size() const { return int(nodes.size()); }

private:
	CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}

public:

	// min-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
		std::vector<Node> nodes(v.size()*2+1);
		std::vector<int> stk; stk.reserve(v.size());
		int root = -1;
		for (int i = 0; i <= int(v.size()); i++) {
			int cur = 2*i;
			nodes[cur].l = i;
			nodes[cur].r = i-1;
			nodes[cur].m = i-1;
			nodes[cur].c = {-1, -1};
			while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
				int nxt = stk.back(); stk.pop_back();
				nodes[cur].p = nxt;
				nodes[nxt].c[1] = cur;
				nodes[nxt].r = nodes[cur].r;
				cur = nxt;
			}
			if (i == int(v.size())) {
				root = cur;
				break;
			}
			nodes[2*i+1].l = nodes[cur].l;
			nodes[2*i+1].m = i;
			nodes[cur].p = 2*i+1;
			nodes[2*i+1].c[0] = cur;
			stk.push_back(2*i+1);
		}
		nodes[root].p = -1;
		return {std::move(nodes), root};
	}

	// max-cartesian-tree, with earlier cells tiebroken earlier
	template <typename T, typename Comp = std::less<T>>
	static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
		return build_min_tree(v, reverse_comparator(comp));
	}
};
#line 7 "verify/cartesian_tree.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N; std::cin >> N;
	std::vector<int> A(N); for (auto& a : A) std::cin >> a;

	auto ct = CartesianTree::build_min_tree(A);
	for (int i = 0; i < N; i++) {
		int p = ct[2*i+1].p;
		if (p == -1) {
			p = i;
		} else {
			assert(p & 1);
			p /= 2;
		}
		std::cout << p << " \n"[i+1==N];
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/reverse_comparator.hpp
template<typename F>struct reverse_comparator_t{
F f;
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
};
template<typename F>constexpr reverse_comparator_t<std::decay_t<F>>reverse_comparator(F&&f){
return{std::forward<F>(f)};
}
// src/cartesian_tree.hpp
class CartesianTree{
public:
struct Node{
int l,m,r;
std::array<int,2>c;
int p;
};
std::vector<Node>nodes;
int root=-1;
CartesianTree(){}
Node&operator[](int idx){return nodes[idx];}
const Node&operator[](int idx)const{return nodes[idx];}
int size()const{return int(nodes.size());}
private:
CartesianTree(std::vector<Node>&&nodes_,int root_):nodes(std::move(nodes_)),root(root_){}
public:
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_min_tree(const std::vector<T>&v,Comp comp=Comp()){
std::vector<Node>nodes(v.size()*2+1);
std::vector<int>stk;stk.reserve(v.size());
int root=-1;
for(int i=0;i<=int(v.size());i++){
int cur=2*i;
nodes[cur].l=i;
nodes[cur].r=i-1;
nodes[cur].m=i-1;
nodes[cur].c={-1,-1};
while(!stk.empty()&&(i==int(v.size())||comp(v[i],v[nodes[stk.back()].m]))){
int nxt=stk.back();stk.pop_back();
nodes[cur].p=nxt;
nodes[nxt].c[1]=cur;
nodes[nxt].r=nodes[cur].r;
cur=nxt;
}
if(i==int(v.size())){
root=cur;
break;
}
nodes[2*i+1].l=nodes[cur].l;
nodes[2*i+1].m=i;
nodes[cur].p=2*i+1;
nodes[2*i+1].c[0]=cur;
stk.push_back(2*i+1);
}
nodes[root].p=-1;
return{std::move(nodes),root};
}
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_max_tree(const std::vector<T>&v,Comp comp=Comp()){
return build_min_tree(v,reverse_comparator(comp));
}
};
// verify/cartesian_tree.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
int N;std::cin>>N;
std::vector<int>A(N);for(auto&a:A)std::cin>>a;
auto ct=CartesianTree::build_min_tree(A);
for(int i=0;i<N;i++){
int p=ct[2*i+1].p;
if(p==-1){
p=i;
}else{
assert(p&1);
p/=2;
}
std::cout<<p<<" \n"[i+1==N];
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env	Name	Status	Elapsed	Memory
g++-sanitizer	almost-decreasing_00	AC	452 ms	68 MB
g++-sanitizer	almost-decreasing_01	AC	114 ms	37 MB
g++-sanitizer	almost-increasing_00	AC	222 ms	72 MB
g++-sanitizer	almost-increasing_01	AC	108 ms	39 MB
g++-sanitizer	decreasing_00	AC	228 ms	68 MB
g++-sanitizer	decreasing_01	AC	124 ms	37 MB
g++-sanitizer	example_00	AC	16 ms	8 MB
g++-sanitizer	example_01	AC	16 ms	8 MB
g++-sanitizer	increasing_00	AC	232 ms	71 MB
g++-sanitizer	increasing_01	AC	117 ms	39 MB
g++-sanitizer	random_00	AC	260 ms	68 MB
g++-sanitizer	random_01	AC	130 ms	37 MB
g++-sanitizer	random_02	AC	164 ms	43 MB
g++-sanitizer	random_03	AC	112 ms	35 MB
g++-sanitizer	random_04	AC	191 ms	57 MB
g++-sanitizer	small_00	AC	16 ms	8 MB
g++-sanitizer	small_01	AC	16 ms	8 MB
g++-sanitizer	small_02	AC	17 ms	8 MB
g++-sanitizer	small_03	AC	13 ms	8 MB
g++-sanitizer	small_04	AC	16 ms	8 MB
g++-sanitizer	small_05	AC	14 ms	8 MB
g++-sanitizer	small_06	AC	16 ms	8 MB
g++-sanitizer	small_07	AC	17 ms	8 MB
g++-sanitizer	small_08	AC	12 ms	8 MB
g++-sanitizer	small_09	AC	18 ms	8 MB
g++	almost-decreasing_00	AC	128 ms	54 MB
g++	almost-decreasing_01	AC	59 ms	27 MB
g++	almost-increasing_00	AC	141 ms	58 MB
g++	almost-increasing_01	AC	63 ms	29 MB
g++	decreasing_00	AC	129 ms	54 MB
g++	decreasing_01	AC	60 ms	27 MB
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	increasing_00	AC	132 ms	58 MB
g++	increasing_01	AC	62 ms	29 MB
g++	random_00	AC	148 ms	54 MB
g++	random_01	AC	64 ms	27 MB
g++	random_02	AC	85 ms	33 MB
g++	random_03	AC	64 ms	25 MB
g++	random_04	AC	120 ms	44 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	4 MB

Back to top page