#624668 (C++17) No.1115 二つの数列 / Two Sequences

提出ソース

結果

問題	No.1115 二つの数列 / Two Sequences
ユーザー	tkmst201
提出日時	2021-03-03 17:50:22
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	81 ms / 2,000 ms
コード長	8,054 bytes
コンパイル時間	607 ms
コンパイル使用メモリ	56,768 KB
実行使用メモリ	9,856 KB
最終ジャッジ日時	2024-10-03 06:51:40
合計ジャッジ時間	3,051 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	66 ms 8,832 KB
testcase_04	AC	79 ms 9,728 KB
testcase_05	AC	68 ms 8,832 KB
testcase_06	AC	60 ms 8,320 KB
testcase_07	AC	78 ms 9,728 KB
testcase_08	AC	4 ms 6,820 KB
testcase_09	AC	29 ms 6,912 KB
testcase_10	AC	52 ms 9,856 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	81 ms 9,856 KB
testcase_13	AC	80 ms 9,856 KB
testcase_14	AC	78 ms 9,856 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	7 ms 6,816 KB
testcase_24	AC	26 ms 6,820 KB
testcase_25	AC	56 ms 8,064 KB
testcase_26	AC	13 ms 6,820 KB
testcase_27	AC	33 ms 6,816 KB
testcase_28	AC	44 ms 7,040 KB
testcase_29	AC	60 ms 8,320 KB
testcase_30	AC	74 ms 9,472 KB
testcase_31	AC	18 ms 6,820 KB
testcase_32	AC	12 ms 6,820 KB
testcase_33	AC	47 ms 8,960 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	1 ms 6,816 KB
testcase_36	AC	2 ms 6,820 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	2 ms 6,816 KB
testcase_39	AC	1 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <cstdint>
#include <vector>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/AVL_Tree.hpp
 */
template<typename T>
struct AVL_Tree {
	using size_type = std::size_t;
	using value_type = T;
	using const_reference = const value_type &;
	
private:
	using uint32 = std::uint32_t;
	using int8 = std::int8_t;
	
public:
	struct Node;
	using node_ptr = Node *;
	using const_ptr = const Node * const;
	struct Node {
		value_type val;
		node_ptr par, child[2] {};
		bool is_r;
		int8 height[2] {};
		uint32 size[2] {};
		Node(const_reference x, node_ptr par, bool is_r) : val(x), par(par), is_r(is_r) {}
	};
	
	
private:
	uint32 size_;
	node_ptr root_node;
	node_ptr e_ptr[2];
	
public:
	AVL_Tree() : size_(0), root_node(nullptr), e_ptr{nullptr, nullptr} {}
	
	
	AVL_Tree(const AVL_Tree & rhs) {
		*this = rhs;
	}
	
	AVL_Tree(AVL_Tree && rhs) {
		size_ = rhs.size_;
		rhs.size_ = 0;
		root_node = rhs.root_node;
		rhs.root_node = nullptr;
		std::copy(rhs.e_ptr, rhs.e_ptr + 2, e_ptr);
		std::fill(rhs.e_ptr, rhs.e_ptr + 2, nullptr);
	}
	
	~AVL_Tree() {
		clear();
	}
	
	AVL_Tree & operator =(const AVL_Tree & rhs) {
		if (this != &rhs) {
			this->clear();
			root_node = copy_dfs(rhs.root_node, nullptr);
			size_ = rhs.size_;
			e_ptr[0] = e_ptr[1] = root_node;
			for (int i = 0; i < 2; ++i) while (e_ptr[i]->child[i]) e_ptr[i] = e_ptr[i]->child[i];
		}
		return *this;
	}
	
	AVL_Tree & operator =(AVL_Tree && rhs) {
		if (this != &rhs) {
			this->clear();
			size_ = rhs.size_;
			rhs.size_ = 0;
			root_node = rhs.root_node;
			rhs.root_node = nullptr;
			std::copy(rhs.e_ptr, rhs.e_ptr + 2, e_ptr);
			std::fill(rhs.e_ptr, rhs.e_ptr + 2, nullptr);
		}
		return *this;
	}
	
	bool empty() const noexcept {
		return size_ == 0;
	}
	
	size_type size() const noexcept {
		return size_;
	}
	
	void clear() {
		clear_dfs(root_node);
		root_node = nullptr;
		size_ = 0;
		std::fill(e_ptr, e_ptr + 2, nullptr);
	}
	
	std::vector<value_type> enumerate() const {
		std::vector<value_type> elements;
		elements.reserve(size());
		enumerate_dfs(root_node, elements);
		return elements;
	}
	
	node_ptr begin() const noexcept {
		return e_ptr[0];
	}
	
	node_ptr end() const noexcept {
		return nullptr;
	}
	
	node_ptr find(const_reference x) const noexcept {
		const node_ptr q = lower_bound(x);
		if (q != end() && q->val != x) return end();
		return q;
	}
	
	node_ptr insert(const_reference x) {
		bool ef[2] {};
		node_ptr q = root_node, r = nullptr;
		bool d = false;
		while (q) {
			r = q;
			d = q->val <= x;
			q = q->child[d];
			ef[!d] = true;
		}
		q = new Node(x, r, d);
		++size_;
		for (int i = 0; i < 2; ++i) if (!ef[i]) e_ptr[i] = q;
		if (r) {
			r->size[d] = 1;
			r->height[d] = 1;
			r->child[d] = q;
			update(r);
		}
		else root_node = q;
		return q;
	}
	
	node_ptr erase(const_reference x) noexcept {
		node_ptr q = find(x);
		if (q == end()) return end();
		return erase(q);
	}
	
	node_ptr erase(node_ptr q) noexcept {
		if (!q) return end();
		const node_ptr ret = next(q);
		if (e_ptr[0] == q) e_ptr[0] = next(q);
		if (e_ptr[1] == q) e_ptr[1] = prev(q);
		node_ptr upd = nullptr;
		if (q->child[0] && q->child[1]) {
			node_ptr p = q->child[0];
			while (p->child[1]) p = p->child[1];
			q->val = std::move(p->val);
			q = p;
		}
		const node_ptr r = q->par;
		if (r) upd = r;
		if (q->child[0] || q->child[1]) {
			const node_ptr p = q->child[0] ? q->child[0] : q->child[1];
			if (r) {
				r->size[q->is_r] = q->size[p->is_r];
				r->height[q->is_r] = q->height[p->is_r];
				r->child[q->is_r] = p;
				p->par = r;
				p->is_r = q->is_r;
			}
			else {
				p->par = nullptr;
				root_node = p;
			}
		}
		else if (r) {
			r->size[q->is_r] = 0;
			r->height[q->is_r] = 0;
			r->child[q->is_r] = nullptr;
		}
		else root_node = nullptr;
		delete q;
		--size_;
		if (upd) update(upd);
		return ret;
	}
	
	node_ptr lower_bound(const_reference x) const noexcept {
		node_ptr q = root_node;
		if (!q) return end();
		while (q->child[q->val < x]) q = q->child[q->val < x];
		if (q->val < x) q = next(q);
		return q;
	}
	
	node_ptr upper_bound(const_reference x) const noexcept {
		node_ptr q = root_node;
		if (!q) return end();
		while (q->child[q->val <= x]) q = q->child[q->val <= x];
		if (q->val <= x) q = next(q);
		return q;
	}
	
	size_type count_less_than(const_reference x) const noexcept {
		size_type res = 0;
		node_ptr q = root_node;
		while (q != nullptr) {
			bool r = q->val < x;
			if (r) res += q->size[0] + 1;
			q = q->child[r];
		}
		return res;
	}
	
	size_type count_less_equal(const_reference x) const noexcept {
		size_type res = 0;
		node_ptr q = root_node;
		while (q != nullptr) {
			bool r = q->val <= x;
			if (r) res += q->size[0] + 1;
			q = q->child[r];
		}
		return res;
	}
	
	size_type count(const_reference x) const noexcept {
		return count_less_equal(x) - count_less_than(x);
	}
	
	size_type count_more_than(const_reference x) const noexcept {
		return size() - count_less_equal(x);
	}
	
	size_type count_more_equal(const_reference x) const noexcept {
		return size() - count_less_than(x);
	}
	
	node_ptr k_th_smallest(uint32 k) const noexcept {
		if (k == 0 || size_ < k) return end();
		node_ptr q = root_node;
		while (k != q->size[0] + 1) {
			if (k > q->size[0] + 1) q = q->child[1], k -= q->size[0] + 1;
			else q = q->child[0];
		}
		return q;
	}
	
	node_ptr k_th_largest(uint32 k) const noexcept {
		if (k == 0 || size_ < k) return end();
		return k_th_smallest(size_ - k + 1);
	}
	
	node_ptr next(node_ptr q) const noexcept {
		if (q == end()) return begin();
		return move(q, true);
	}
	
	node_ptr prev(node_ptr q) const noexcept {
		if (q == begin()) return end();
		return move(q, false);
	}
	
private:
	node_ptr copy_dfs(const_ptr q, node_ptr r) {
		if (!q) return nullptr;
		node_ptr res = new Node(q->val, r, q->is_r);
		for (int i = 0; i < 2; ++i) {
			res->height[i] = q->height[i];
			res->size[i] = q->size[i];
			res->child[i] = copy_dfs(q->child[i], res);
		}
		return res;
	}
	
	void clear_dfs(node_ptr q) {
		if (!q) return;
		clear_dfs(q->child[0]);
		clear_dfs(q->child[1]);
		delete q;
	}
	
	void enumerate_dfs(const_ptr q, std::vector<value_type> & elements) const {
		if (!q) return;
		enumerate_dfs(q->child[0], elements);
		elements.emplace_back(q->val);
		enumerate_dfs(q->child[1], elements);
	}
	
	
	node_ptr rotate(node_ptr q, bool d) noexcept {
		node_ptr r = q->par, p = q->child[!d], b = p->child[d];
		(r ? r->child[q->is_r] : root_node) = p;
		q->child[!d] = b;
		p->child[d] = q;
		if (b) {
			b->par = q;
			b->is_r = !d;
		}
		p->par = q->par;
		p->is_r = q->is_r;
		q->par = p;
		q->is_r = d;
		q->size[!d] = p->size[d];
		q->height[!d] = p->height[d];
		p->size[d] = q->size[0] + q->size[1] + 1;
		p->height[d] = std::max(q->height[0], q->height[1]) + 1;
		return p;
	}
	
	void update(node_ptr q) noexcept {
		bool done = false;
		while (true) {
			if (!done && std::abs(q->height[0] - q->height[1]) > 1) {
				const bool d = q->height[0] > q->height[1];
				const node_ptr p = q->child[!d];
				if (p->height[!d] < p->height[d]) rotate(p, !d);
				q = rotate(q, d);
				done = true;
			}
			const node_ptr r = q->par;
			if (!r) break;
			r->size[q->is_r] = q->size[0] + q->size[1] + 1;
			r->height[q->is_r] = std::max(q->height[0], q->height[1]) + 1;
			q = r;
		}
	}
	
	node_ptr move(node_ptr q, bool d) const noexcept {
		if (q == end()) return e_ptr[!d];
		if (q == begin() && !d) return end();
		if (q->child[d]) for (q = q->child[d]; q->child[!d]; q = q->child[!d]);
		else {
			while (q && (d ^ !q->is_r)) q = q->par;
			if (q) q = q->par;
		}
		return q;
	}
};

#include <cstdio>
#include <vector>

int main() {
	int N;
	scanf("%d", &N);
	std::vector<int> A(N), table(N);
	for (int i = 0; i < N; ++i) scanf("%d", &A[i]), --A[i];
	for (int i = 0; i < N; ++i) {
		int b;
		scanf("%d", &b);
		table[b - 1] = i;
	}
	for (int i = 0; i < N; ++i) A[i] = table[A[i]];
	
	long long ans = 0;
	AVL_Tree<int> avl;
	for (int i = 0; i < N; ++i) {
		ans += avl.count_more_than(A[i]);
		avl.insert(A[i]);
	}
	printf("%lld\n", ans);
}

yukicoder

結果

テストケース

ソースコード