#424230 (C++11) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	Div9851
提出日時	2020-01-31 22:58:36
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	12,479 bytes
コンパイル時間	845 ms
コンパイル使用メモリ	59,660 KB
実行使用メモリ	23,192 KB
最終ジャッジ日時	2024-09-17 10:01:04
合計ジャッジ時間	6,737 ms
ジャッジサーバーID （参考情報）	judge6 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	29 ms 7,368 KB
testcase_04	AC	127 ms 23,192 KB
testcase_05	AC	105 ms 19,280 KB
testcase_06	AC	91 ms 19,212 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	AC	85 ms 9,632 KB
testcase_17	AC	97 ms 10,268 KB
testcase_18	AC	136 ms 10,908 KB
testcase_19	AC	119 ms 11,676 KB
testcase_20	AC	134 ms 13,648 KB
testcase_21	AC	145 ms 13,308 KB
testcase_22	AC	158 ms 14,156 KB
testcase_23	AC	163 ms 15,548 KB
testcase_24	AC	177 ms 14,984 KB
testcase_25	AC	191 ms 15,608 KB
testcase_26	WA	-
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	RE	-
testcase_31	RE	-
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,944 KB

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

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:443:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  443 |         scanf("%d %d", &Q, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:448:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  448 |                 scanf("%d", &t);
      |                 ~~~~~^~~~~~~~~~
main.cpp:451:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  451 |                         scanf("%lld", &v);
      |                         ~~~~~^~~~~~~~~~~~

ソースコード

raw source code

#include <cstdio>
#include <cassert>
#include <climits>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

const int degree = 3;

struct BPlusTreeNode {
	int keys[degree];
	int count[degree + 1];
	int total;
	BPlusTreeNode* pointers[degree + 1];
	bool is_leaf;
	int size;

	BPlusTreeNode() {
		for (int i = 0; i < degree; i++) keys[i] = 0;
		for (int i = 0; i <= degree; i++) count[i] = 0;
		for (int i = 0; i <= degree; i++) pointers[i] = NULL;
		total = 0;
		is_leaf = 0;
		size = 0;
	}

	BPlusTreeNode* insert_key(int key) {
		if (is_leaf) return insert_key_to_leaf(key);
		return insert_key_to_node(key);
	}

	BPlusTreeNode* insert_key_to_node(int key) {
		assert(!is_leaf);
		int pos = size;
		while (pos > 0 && keys[pos - 1] > key) pos--;
		total -= count[pos];
		BPlusTreeNode* ret = pointers[pos]->insert_key(key);
		count[pos] = pointers[pos]->total;
		total += count[pos];
		if (ret == NULL) return NULL;
		return insert_node_to_node(pos, ret);
	}

	BPlusTreeNode* insert_node_to_node(int index, BPlusTreeNode *node) {
		assert(!is_leaf);
		if (size < degree) {
			insert_node_to_node_no_split(index, node);
			return NULL;
		}
		return insert_node_to_node_split(index, node);
	}

	BPlusTreeNode* insert_node_to_node_split(int index, BPlusTreeNode *node) {
		assert(!is_leaf);
		assert(size == degree);
		BPlusTreeNode* right = new BPlusTreeNode();
		bool node_inserted = 0;
		int pos = size;
		while (pos >= 0 && (right->size + 1) < (degree + 2) / 2) {
			if (pos == index && !node_inserted) {
				right->insert_node_to_node_head(node);
				node_inserted = 1;
				continue;
			}
			right->insert_node_to_node_head(pointers[pos]);
			delete_last_node_from_node();
			pos--;
		}
		if (!node_inserted) insert_node_to_node_no_split(index, node);
		return right;
	}

	void insert_node_to_node_no_split(int index, BPlusTreeNode *node) {
		assert(!is_leaf);
		assert(size < degree);
		for (int i = size ; i > index; i--) {
			keys[i] = keys[i - 1];
			count[i + 1] = count[i];
			pointers[i + 1] = pointers[i];
		}
		keys[index] = node->minimum_key();
		count[index + 1] = node->total;
		total += count[index + 1];
		pointers[index + 1] = node;
		size++;
	}

	void insert_node_to_node_head(BPlusTreeNode *node) {
		assert(!is_leaf);
		assert(size < degree);
		for (int i = size; i >= 0; i--) {
			count[i + 1] = count[i];
			pointers[i + 1] = pointers[i];
		}
		for (int i = size; i > 0; i--) keys[i] = keys[i - 1];
		if (pointers[1] != NULL) {
			keys[0] = pointers[1]->minimum_key();
			size++;
		}
		count[0] = node->total;
		total += count[0];
		pointers[0] = node;
	}

	BPlusTreeNode* insert_key_to_leaf(int key) {
		assert(is_leaf);
		if (size < degree) {
			insert_key_to_leaf_no_split(key);
			return NULL;
		}
		return insert_key_to_leaf_split(key);
	}

	BPlusTreeNode* insert_key_to_leaf_split(int key) {
		assert(is_leaf);
		assert(size == degree);
		BPlusTreeNode* right = new BPlusTreeNode();
		right->is_leaf = 1;
		bool key_inserted = 0;
		int pos = size - 1;
		while (pos >= 0 && (right->size) < (degree + 1) / 2) {
			if (keys[pos] < key && !key_inserted) {
				right->insert_key_to_leaf_no_split(key);
				key_inserted = 1;
				continue;
			}
			right->insert_key_to_leaf_no_split(keys[pos]);
			delete_last_key_from_leaf();
			pos--;
		}
		if (!key_inserted) insert_key_to_leaf_no_split(key);
		right->pointers[degree] = pointers[degree];
		if (pointers[degree] != NULL) pointers[degree]->pointers[0] = right;
		pointers[degree] = right;
		right->pointers[0] = this;

		return right;
	}

	void insert_key_to_leaf_no_split(int key) {
		assert(is_leaf);
		assert(size < degree);
		int pos = size;
		while (pos > 0 && keys[pos - 1] > key) {
			keys[pos] = keys[pos - 1];
			pos--;
		}
		keys[pos] = key;
		total++;
		size++;
	}

	void delete_key(int key) {
		if (is_leaf) delete_key_from_leaf(key);
		else delete_key_from_node(key);
	}

	void delete_key_from_node(int key) {
		assert(!is_leaf);
		int pos = size;
		while (pos > 0 && keys[pos - 1] > key) pos--;
		total--;
		count[pos]--;
		pointers[pos]->delete_key(key);
		if (pointers[pos]->is_leaf) fix_leaf(pos);
		else fix_node(pos);
	}

	void fix_leaf(int index) {
		assert(pointers[index]->is_leaf);
		if (pointers[index]->size >= (degree + 1) / 2) {
			count[index] = pointers[index]->total;
			if (index > 0) keys[index - 1] = pointers[index]->minimum_key();
			return;
		}
		if (index > 0 && pointers[index - 1]->size > (degree + 1) / 2) { // 左隣から借りる
			BPlusTreeNode* left = pointers[index - 1];
			pointers[index]->insert_key_to_leaf_no_split(left->keys[left->size - 1]);
			left->delete_last_key_from_leaf();
			count[index]++;
			count[index - 1]--;
			keys[index - 1] = pointers[index]->minimum_key();
			return;
		}
		if (index < size && pointers[index + 1]->size >(degree + 1) / 2) { // 右隣から借りる
			BPlusTreeNode* right = pointers[index + 1];
			pointers[index]->insert_key_to_leaf_no_split(right->keys[0]);
			right->delete_first_key_from_leaf();
			count[index]++;
			count[index + 1]--;
			keys[index] = right->minimum_key();
			return;
		}
		if (index > 0) { // 左隣とマージする
			BPlusTreeNode* left = pointers[index - 1];
			while (pointers[index]->size > 0) {
				left->insert_key_to_leaf_no_split(pointers[index]->keys[pointers[index]->size - 1]);
				pointers[index]->delete_last_key_from_leaf();
			}
			count[index - 1] = pointers[index - 1]->total;
			if (pointers[index]->pointers[degree] != NULL) pointers[index]->pointers[degree]->pointers[0] = pointers[index - 1];
			pointers[index - 1]->pointers[degree] = pointers[index]->pointers[degree];
			for (int i = index; i + 1 <= size; i++) {
				keys[i - 1] = keys[i];
				count[i] = count[i + 1];
				pointers[i] = pointers[i + 1];
			}
			if (index > 1) keys[index - 2] = left->minimum_key();
			keys[size - 1] = 0;
			count[size] = 0;
			pointers[size] = NULL;
			size--;
			return;
		}
		// 右隣とマージする（index = 0の場合のみ）
		BPlusTreeNode* right = pointers[index + 1];
		while (pointers[index]->size > 0) {
			right->insert_key_to_leaf_no_split(pointers[index]->keys[pointers[index]->size - 1]);
			pointers[index]->delete_last_key_from_leaf();
		}
		count[index + 1] = pointers[index + 1]->total;
		if (pointers[index]->pointers[0] != NULL) pointers[index]->pointers[0]->pointers[degree] = pointers[index + 1];
		pointers[index + 1]->pointers[0] = pointers[index]->pointers[0];
		for (int i = index; i + 1 <= size; i++) {
			keys[i - 1] = keys[i];
			count[i] = count[i + 1];
			pointers[i] = pointers[i + 1];
		}
		keys[size - 1] = 0;
		count[size] = 0;
		pointers[size] = NULL;
		size--;
	}

	void fix_node(int index) {
		assert(!pointers[index]->is_leaf);
		if (pointers[index]->size + 1 >= (degree + 2) / 2) {
			count[index] = pointers[index]->total;
			if (index > 0) keys[index - 1] = pointers[index]->minimum_key();
			return;
		}
		if (index > 0 && pointers[index - 1]->size + 1 > (degree + 2) / 2) { // 左隣から借りる
			BPlusTreeNode* left = pointers[index - 1];
			pointers[index]->insert_node_to_node_head(left->pointers[left->size]);
			left->delete_last_node_from_node();
			count[index - 1] = left->total;
			count[index] = pointers[index]->total;
			keys[index - 1] = pointers[index]->minimum_key();
			return;
		}
		if (index < size && pointers[index + 1]->size + 1 >(degree + 2) / 2) { // 右隣から借りる
			BPlusTreeNode* right = pointers[index + 1];
			pointers[index]->insert_node_to_node_no_split(pointers[index]->size, right->pointers[0]);
			right->delete_first_node_from_node();
			count[index + 1] = right ->total;
			count[index] = pointers[index]->total;
			keys[index] = right ->minimum_key();
			return;
		}
		if (index > 0) { // 左隣とマージする
			BPlusTreeNode* left = pointers[index - 1];
			while (pointers[index]->size >= 0) {
				left->insert_node_to_node(left->size, pointers[index]->pointers[0]);
				if(pointers[index]->size > 0) pointers[index]->delete_first_node_from_node();
				else break;
			}
			count[index - 1] = pointers[index - 1]->total;
			for (int i = index; i + 1 <= size; i++) {
				keys[i - 1] = keys[i];
				count[i] = count[i + 1];
				pointers[i] = pointers[i + 1];
			}
			if (index > 1) keys[index - 2] = left->minimum_key();
			keys[size - 1] = 0;
			count[size] = 0;
			pointers[size] = NULL;
			size--;
			return;
		}
		// 右隣とマージする（index = 0の場合のみ）
		BPlusTreeNode* right = pointers[index + 1];
		while(pointers[index]->size >= 0) {
			right->insert_node_to_node_head(pointers[index]->pointers[pointers[index]->size]);
			if (pointers[index]->size > 0) pointers[index]->delete_last_node_from_node();
			else break;
		}
		count[index + 1] = pointers[index + 1]->total;
		for (int i = index; i + 1 <= size; i++) {
			keys[i - 1] = keys[i];
			count[i] = count[i + 1];
			pointers[i] = pointers[i + 1];
		}
		keys[size - 1] = 0;
		count[size] = 0;
		pointers[size] = NULL;
		size--;
	}

	void delete_key_from_leaf(int key) {
		assert(is_leaf);
		int pos = 0;
		while (pos < size) {
			if (keys[pos] == key) break;
			pos++;
		}
		assert(pos < size);
		for (int i = pos; i + 1 < size; i++) keys[i] = keys[i + 1];
		keys[size - 1] = 0;
		total--;
		size--;
	}

	void delete_last_key_from_leaf() {
		assert(is_leaf);
		assert(size > 0);
		keys[size - 1] = 0;
		total--;
		size--;
	}

	void delete_first_key_from_leaf() {
		assert(is_leaf);
		assert(size > 0);
		for (int i = 1; i < size; i++) keys[i - 1] = keys[i];
		keys[size - 1] = 0;
		total--;
		size--;
	}

	void delete_last_node_from_node() {
		assert(!is_leaf);
		assert(size > 0);
		keys[size - 1] = 0;
		pointers[size] = NULL;
		total -= count[size];
		count[size] = 0;
		size--;
	}

	void delete_first_node_from_node() {
		assert(!is_leaf);
		assert(size > 0);
		total -= count[0];
		for (int i = 1; i < size; i++) keys[i - 1] = keys[i];
		for (int i = 1; i <= size; i++) {
			count[i - 1] = count[i];
			pointers[i - 1] = pointers[i];
		}
		keys[size - 1] = 0;
		count[0] = 0;
		pointers[size] = NULL;
		size--;
	}

	int minimum_key() {
		if (is_leaf) {
			assert(size > 0);
			return keys[0];
		}
		assert(pointers[0] != NULL);
		return pointers[0]->minimum_key();
	}
};

struct BPlusTree {
	BPlusTreeNode* root;
	BPlusTree() {
		root = new BPlusTreeNode();
		root->is_leaf = 1;
	}
	void insert_key(int key) {
		BPlusTreeNode* ret = root->insert_key(key);
		if (ret != NULL) {
			BPlusTreeNode* new_root = new BPlusTreeNode();
			new_root->insert_node_to_node_head(root);
			new_root->insert_node_to_node_no_split(0, ret);
			root = new_root;
		}
	}

	void delete_key(int key) {
		root->delete_key(key);
		if (root->size == 0 && !root->is_leaf) root = root->pointers[0];
	}

	std::pair<BPlusTreeNode*, int> find(int key) {
		BPlusTreeNode* now = root;
		while (!now->is_leaf) {
			int pos = now->size;
			while (pos > 0 && now->keys[pos - 1] > key) pos--;
			now = now->pointers[pos];
		}
		bool is_included = 0;
		for (int i = 0; i < now->size; i++) {
			if (now->keys[i] == key) return std::make_pair(now, i);
		}
		return std::make_pair((BPlusTreeNode*) NULL, -1);
	}

	// 0-indexed
	int get_kth(int k) {
		BPlusTreeNode* now = root;
		while (!now->is_leaf) {
			int pos = 0;
			int sum = 0;
			while (pos < now->size && (sum + now->count[pos]) <= k) {
				sum += now->count[pos];
				pos++;
			}
			now = now->pointers[pos];
			k -= sum;
		}
		return now->keys[k];
	}

	int size() {
		return root->total;
	}
};

/*int main() {
	int Q;
	scanf("%d", &Q);
	BPlusTree btree;
	for (int i = 0; i < Q; i++) {
		int T, X;
		scanf("%d %d", &T, &X);
		if (T == 1) {
			btree.insert_key(X);
		}
		else {
			X--;
			int v = btree.get_kth(X);
			printf("%d\n", v);
			btree.delete_key(v);
		}
	}
}*/

int main() {
	int Q, K;
	scanf("%d %d", &Q, &K);
	vector<pair<int, long long>> query;
	vector<long long> vec;
	for (int i = 0; i < Q; i++) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			long long v;
			scanf("%lld", &v);
			query.emplace_back(1, v);
			vec.push_back(v);
		}
		else {
			query.emplace_back(2, -1);
		}
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	BPlusTree btree;
	for (int i = 0; i < Q; i++) {
		if (query[i].first == 1) {
			int idx = lower_bound(vec.begin(), vec.end(), query[i].second) - vec.begin();
			btree.insert_key(idx);
		}
		else {
			if (btree.size() < K) {
				printf("-1\n");
				continue;
			}
			int idx = btree.get_kth(K - 1);
			printf("%lld\n", vec[idx]);
			btree.delete_key(idx);
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード