Submission #246373

#	Time	Username	Problem	Language	Result	Execution time	Memory
246373		ant101	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	704 ms	155768 KiB

scrivener

#include <bits/stdc++.h>
#define N 1000050
#define log 22
using namespace std;
 
int n, id;
 
struct node
{
	char c;
 
	node *anc[log];
 
	int sz;
 
	node()
	{
		for(int i = 0; i < log ; i++) anc[i] = NULL;
 
		sz = 0;
	}
};
 
node *tree[N];
 
void TypeLetter(char c)
{
	int tmp = ++id;
 
	if(!tree[tmp]) tree[tmp] = new node();
 
	tree[tmp]->c = c;
 
	tree[tmp]->anc[0] = tree[tmp - 1];
 
	for(int i = 1; i < log; i++)
	{
	 	(tree[tmp]->anc[i]) = (tree[tmp]->anc[i - 1] ? (tree[tmp]->anc[i - 1])->anc[i - 1] : NULL);
	}
 
	tree[tmp]->sz = tree[tmp - 1]->sz + 1;
}
 
void UndoCommands(int k)
{
	int tmp = ++id;
 
	tree[tmp] = tree[tmp - k - 1];
}
 
char GetLetter(int k)
{	
	int tmp = id;
 
	node *root = tree[tmp];
 
	int up = root->sz - k - 1;
 
	for(int i = log - 1; i >= 0; i--)
	{
		if(up - (1<<i) >= 0)
		{
			up -= (1<<i);
 
			root = root->anc[i];
		}
	}
 
	return root->c;
}
 
void Init()
{
	id = 0;
 
	tree[0] = new node();
}

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