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

int main() {
	using namespace std;
	using namespace chrono;
	using namespace __gnu_pbds;
	using clock = high_resolution_clock;
	const int M = 2, N = 2e4;
	using ivec = array<int,N>;
	using imat = array<ivec,M>;
	using iset = set<int>;
	mt19937 random(clock::now().time_since_epoch().count());
	set<int> s; 
	tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> t;
	const function<int(int)> tester[] = {
		[&](int x){ return int(distance(s.begin(),s.find(x))); },
		[&](int x){ return int(t.order_of_key(x)); } };
	int v[N], result[M][N];
	const auto test_set = [&](const string& prompt, int i) {
		const auto t0 = clock::now();
		const auto& f = tester[i];
		for (int j = 0; j < N; ++j)
			result[i][j] = f(v[j]);
		const auto t1 = clock::now();
		const auto time = duration_cast<milliseconds>(t1-t0).count();
		cout << prompt << ": elapsed time = " << time << " msec." << endl; };
	for (int x, size = 0; size < N; )
		if (x = random(), s.find(x) == s.end())
			s.insert(x), t.insert(x), v[size++] = x;
	shuffle(v,v+N,random), test_set("iset",0), test_set("oset",1);
	for (int j = 0; j < N; ++j)
		if (result[0][j] != result[1][j])
			cout << "Failed.", exit(0);
	cout << "Passed"; }