Submission #785651

#	Time	Username	Problem	Language	Result	Execution time	Memory
785651		MODDI	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	557 ms	105932 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
int up[1000005][24], dep[1000005], pos[1000005];
char bukva[1000005];
int cur, i, n;


void Init() {
	n = 0;
	pos[0] = 0;
	dep[0] = -1;
	for(int i = 0; i < 24; i++)	up[0][i] = 0;
}

void TypeLetter(char L) {
	++n;
	pos[n] = n;
	bukva[n] = L;
	dep[n] = dep[pos[n-1]]+1;
	up[n][0] = pos[n-1];
	for(int i = 1; i < 24; i++)	up[n][i] = up[up[n][i-1]][i-1];
}

void UndoCommands(int U) {
	++n;
	pos[n] = pos[n-1-U];
}

char GetLetter(int P) {
	cur = pos[n];
	for(int i = 23; i >=0; --i){
		if(dep[up[cur][i]] >= P)	cur = up[cur][i];
	}
	return bukva[cur];
}

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