Submission #1238694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238694		xnqs	Crayfish scrivener (IOI12_scrivener)	C++20	34 / 100	503 ms	327680 KiB

scrivener

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

struct SegTreeNode {
	char val = '0';
	SegTreeNode* l = nullptr;
	SegTreeNode* r = nullptr;
};

namespace mempool {
	//SegTreeNode pool[15000005];
	//int idx = 0;

	SegTreeNode* new_node() {
		return new SegTreeNode;
		//return pool + idx++;
	}
}

int roots = 0;
int depth[1000005];
SegTreeNode* root[1000005];
std::vector<int> stk;

inline char get_val(SegTreeNode* node) {
	if (!node) {
		return 0;
	}
	return node->val;
}

inline SegTreeNode* get_l(SegTreeNode* node) {
	if (!node) {
		return nullptr;
	}
	return node->l;
}

inline SegTreeNode* get_r(SegTreeNode* node) {
	if (!node) {
		return nullptr;
	}
	return node->r;
}

SegTreeNode* update(SegTreeNode* root, int l, int r, int pos, char val) {
	SegTreeNode* ret = mempool::new_node();
	ret->l = get_l(root);
	ret->r = get_r(root);
	if (l == r) {
		ret->val = val;
		return ret;
	}

	int m = (l+r)>>1;
	if (pos <= m) {
		ret->l = update(ret->l, l, m, pos, val);
	}
	else {
		ret->r = update(ret->r, m+1, r, pos, val);
	}

	return ret;
}

// this assumes that the path in question exists, which should always be the case
char query(SegTreeNode* root, int l, int r, int pos) {
	if (l == r) {
		return root->val;
	}

	int m = (l+r)>>1;
	if (pos <= m) {
		return query(root->l, l, m, pos);
	}
	else {
		return query(root->r, m+1, r, pos);
	}
}

void Init() {
	roots = 1;
	root[0] = mempool::new_node();
	depth[0] = 0;
	stk.emplace_back(0);
}

void TypeLetter(char L) {
	int old_root = stk.back();
	int new_root = roots;
	depth[new_root] = depth[old_root] + 1;
	root[new_root] = update(root[old_root], 1, 1000000, depth[new_root], L);
	stk.emplace_back(new_root);
	++roots;

	//std::cout << stk.size() << "\n";
}

void UndoCommands(int U) {
	int curr_state = stk.back();
	int new_state = stk[stk.size()-1-U];
	stk.pop_back();
	stk.emplace_back(curr_state);
	stk.emplace_back(new_state);

	//std::cout << stk.size() << "\n";
}

char GetLetter(int P) {
	int curr_state = stk.back();
	//std::cout << depth[curr_state] << " " << P+1 << "\n";
	return query(root[curr_state], 1, 1000000, P+1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40