1 files changed, 58 insertions, 17 deletions

diff --git a/test/util.h b/test/util.h
index 8de393d..98fd7f6 100644
--- a/test/util.h
+++ b/test/util.h
@@ -1,16 +1,16 @@
+#ifdef SANITIZE
+# define _GLIBCXX_ASSERTIONS 1
+# define _GLIBCXX_SANITIZE_VECTOR 1
+#endif
 #include <bits/stdc++.h>
 using namespace std;
 
-#define all(x) std::begin(x), std::end(x)
-#define sz(x) (ll)std::size(x)
-
 #ifdef SANITIZE
 	constexpr bool sanitize = true;
 #else
 	constexpr bool sanitize = false;
 #endif
 
-
 using ll = long long;
 using lll = __int128;
 using ld = long double;
@@ -20,6 +20,16 @@ namespace INT {constexpr int INF = 0x3FFF'FFFF;}
 namespace LL {constexpr ll INF = 0x3FFF'FFFF'FFFF'FFFFll;}
 namespace LD {constexpr ld INF = numeric_limits<ld>::infinity();}
 
+#ifdef SANITIZE
+template<typename T>
+T _lg_check(T n) {
+	assert(n > 0);
+	return __lg(n);
+}
+
+#define __lg _lg_check
+#endif
+
 namespace details {
 	template<typename T = ll>
 	bool isPrime(T x) {
@@ -116,7 +126,7 @@ namespace Random {
 
 	std::string string(std::size_t n, string_view chars) {
 		std::string res(n, '*');
-		for (char& c : res) c = chars[integer(sz(chars))];
+		for (char& c : res) c = chars[integer(ssize(chars))];
 		return res;
 	}
 
@@ -175,6 +185,30 @@ namespace Random {
 	exit(1);
 }
 
+namespace detail {
+	double benchmark() {
+		mt19937 rng(734820734);
+		vector<unsigned> a(10000000);
+		for (unsigned &x: a) x = rng();
+		chrono::steady_clock::time_point start = chrono::steady_clock::now();
+		vector<unsigned> dp(ssize(a)+1, numeric_limits<unsigned>::max());
+		int res = 0;
+		for (unsigned x: a) {
+			auto it = ranges::upper_bound(dp, x);
+			res = max(res, (int)(it - begin(dp)));
+			*it = x;
+		}
+		chrono::steady_clock::time_point end = chrono::steady_clock::now();
+		assert(res == 6301);
+		double t =
+		  chrono::duration_cast<chrono::duration<double, milli>>(end - start)
+		    .count();
+		return 30/t;
+	}
+
+	double speed = sanitize ? numeric_limits<double>::infinity() : benchmark();
+}
+
 struct timer {
 	bool running = false;
 	double time = 0;
@@ -190,7 +224,7 @@ struct timer {
 		auto end = chrono::steady_clock::now();
 		if (!running) cerr << "timer not running!" << FAIL;
 		running = false;
-		time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count();
+		time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count() * detail::speed;
 	}
 
 	void reset() {
@@ -215,7 +249,7 @@ namespace c20 {
 			return {{a[I]...}};
 		}
 	}
- 
+
 	template<class T, std::size_t N>
 	constexpr std::array<std::remove_cv_t<T>, N> to_array(T (&a)[N]) {
 		return c20::detail::to_array_impl(a, std::make_index_sequence<N>{});
@@ -264,9 +298,9 @@ public:
 
 	Graph(int n) : adj(n) {}
 
-	int m() const {return sz(edges);}
-	int n() const {return sz(adj);}
-	int deg(int x) const {return sz(adj[x]);}
+	int m() const {return ssize(edges);}
+	int n() const {return ssize(adj);}
+	int deg(int x) const {return ssize(adj[x]);}
 
 	Graph& clear() {
 		adj.assign(adj.size(), {});
@@ -278,33 +312,33 @@ public:
 		if (!LOOPS && from == to) return false;
 		if (!MULTI && adj[from].find(to) != adj[from].end()) return false;
 		edges.emplace_back(from, to, w);
-		_addAdj(sz(edges) - 1);
+		_addAdj(ssize(edges) - 1);
 		return true;
 	}
 
 	Graph& reverse() {
 		for (auto& e : edges) swap(e.from, e.to);
 		adj.assign(adj.size(), {});
-		for (int i = 0; i < sz(edges); i++) _addAdj(i);
+		for (int i = 0; i < ssize(edges); i++) _addAdj(i);
 		return *this;
 	}
 
 	Graph& shuffle() {
-		std::shuffle(all(edges), Random::rng);
+		ranges::shuffle(edges, Random::rng);
 		if constexpr (!DIR) {
 			for (auto& e : edges) {
 				if (Random::integer(0, 2)) swap(e.from, e.to);
 			}
 		}
 		adj.assign(adj.size(), {});
-		for (int i = 0; i < sz(edges); i++) _addAdj(i);
+		for (int i = 0; i < ssize(edges); i++) _addAdj(i);
 		return *this;
 	}
 
 	Graph& permutate() {
 		vector<int> perm(n());
-		iota(all(perm), 0);
-		std::shuffle(all(perm), Random::rng);
+		iota(begin(perm), end(perm), 0);
+		ranges::shuffle(perm, Random::rng);
 		for (auto& e : edges) {
 			e.from = perm[e.from];
 			e.to = perm[e.to];
@@ -382,7 +416,7 @@ public:
 						}
 					}
 				}
-				std::shuffle(all(tmp), Random::rng);
+				ranges::shuffle(tmp, Random::rng);
 				for (auto [a, b] : tmp) {
 					if (todo <= 0) break;
 					if (addEdge(a, b)) todo--;
@@ -420,3 +454,10 @@ ld float_error(ld given, ld expected) {
 	}
 	return numeric_limits<ld>::infinity();
 }
+
+#include <ext/pb_ds/assoc_container.hpp>
+template<typename T>
+using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>,
+                              __gnu_pbds::rb_tree_tag,
+                              __gnu_pbds::tree_order_statistics_node_update>;
+