test/yosupo/cartesian_tree.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian-Tree (src/Misc/CartesianTree.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/CartesianTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> a(N);
 for (int i= 0; i < N; ++i) cin >> a[i];
 CartesianTree ct(a);
 for (int i= 0; i < N; ++i) cout << (ct.parent(i) == -1 ? i : ct.parent(i)) << " \n"[i == N - 1];
 return 0;
}

#line 1 "test/yosupo/cartesian_tree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Misc/CartesianTree.hpp"
#include <array>
class CartesianTree {
 std::vector<std::array<int, 2>> rg, ch;
 std::vector<int> par;
 int rt;
public:
 template <class Vec> CartesianTree(const Vec &a, bool is_min= 1): rg(a.size()), ch(a.size(), std::array{-1, -1}), par(a.size(), -1) {
  const int n= a.size();
  auto comp= [&](int l, int r) { return (is_min ? a[l] < a[r] : a[l] > a[r]) || (a[l] == a[r] && l < r); };
  int st[n], t= 0;
  for (int i= n; i--; rg[i][1]= (t ? st[t - 1] : n), st[t++]= i)
   while (t && comp(i, st[t - 1])) ch[i][1]= st[--t];
  for (int i= t= 0; i < n; rg[i][0]= (t ? st[t - 1] + 1 : 0), st[t++]= i++)
   while (t && comp(i, st[t - 1])) ch[i][0]= st[--t];
  for (int i= 0; i < n; ++i)
   for (int b= 2; b--;)
    if (ch[i][b] != -1) par[ch[i][b]]= i;
  for (int i= 0; i < n; ++i)
   if (par[i] == -1) rt= i;
 }
 std::array<int, 2> children(int i) const { return ch[i]; }
 int parent(int i) const { return par[i]; }
 int root() const { return rt; }
 // [l,r)
 std::array<int, 2> range(int i) const { return rg[i]; }
};
#line 7 "test/yosupo/cartesian_tree.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> a(N);
 for (int i= 0; i < N; ++i) cin >> a[i];
 CartesianTree ct(a);
 for (int i= 0; i < N; ++i) cout << (ct.parent(i) == -1 ? i : ct.parent(i)) << " \n"[i == N - 1];
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	almost-decreasing_00	AC	116 ms	31 MB
g++-13	almost-decreasing_01	AC	60 ms	16 MB
g++-13	almost-increasing_00	AC	117 ms	31 MB
g++-13	almost-increasing_01	AC	59 ms	16 MB
g++-13	decreasing_00	AC	124 ms	31 MB
g++-13	decreasing_01	AC	60 ms	16 MB
g++-13	example_00	AC	6 ms	4 MB
g++-13	example_01	AC	5 ms	4 MB
g++-13	increasing_00	AC	117 ms	31 MB
g++-13	increasing_01	AC	60 ms	16 MB
g++-13	random_00	AC	137 ms	31 MB
g++-13	random_01	AC	70 ms	16 MB
g++-13	random_02	AC	83 ms	19 MB
g++-13	random_03	AC	64 ms	15 MB
g++-13	random_04	AC	111 ms	25 MB
g++-13	small_00	AC	6 ms	4 MB
g++-13	small_01	AC	5 ms	3 MB
g++-13	small_02	AC	5 ms	4 MB
g++-13	small_03	AC	5 ms	4 MB
g++-13	small_04	AC	5 ms	4 MB
g++-13	small_05	AC	6 ms	3 MB
g++-13	small_06	AC	6 ms	4 MB
g++-13	small_07	AC	5 ms	4 MB
g++-13	small_08	AC	5 ms	4 MB
g++-13	small_09	AC	5 ms	3 MB
clang++-18	almost-decreasing_00	AC	112 ms	31 MB
clang++-18	almost-decreasing_01	AC	58 ms	16 MB
clang++-18	almost-increasing_00	AC	121 ms	31 MB
clang++-18	almost-increasing_01	AC	58 ms	16 MB
clang++-18	decreasing_00	AC	112 ms	31 MB
clang++-18	decreasing_01	AC	64 ms	16 MB
clang++-18	example_00	AC	6 ms	4 MB
clang++-18	example_01	AC	5 ms	4 MB
clang++-18	increasing_00	AC	121 ms	31 MB
clang++-18	increasing_01	AC	66 ms	16 MB
clang++-18	random_00	AC	134 ms	27 MB
clang++-18	random_01	AC	68 ms	14 MB
clang++-18	random_02	AC	80 ms	17 MB
clang++-18	random_03	AC	62 ms	13 MB
clang++-18	random_04	AC	109 ms	22 MB
clang++-18	small_00	AC	8 ms	4 MB
clang++-18	small_01	AC	7 ms	4 MB
clang++-18	small_02	AC	13 ms	4 MB
clang++-18	small_03	AC	6 ms	4 MB
clang++-18	small_04	AC	7 ms	4 MB
clang++-18	small_05	AC	6 ms	4 MB
clang++-18	small_06	AC	6 ms	4 MB
clang++-18	small_07	AC	6 ms	4 MB
clang++-18	small_08	AC	6 ms	4 MB
clang++-18	small_09	AC	6 ms	4 MB

Back to top page