Submission #1001335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001335		ZeroCool	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	507 ms	86608 KiB

scrivener

#include <bits/stdc++.h>
 
using namespace std;


void Init() {}

const int N = 1e6 + 20, LOG = 20;

int n;
int  up[N][LOG], dep[N];
char A[N];

void TypeLetter(char c) {
	++n;
	A[n] = c;
	up[n][0] = n - 1;
	dep[n] = dep[n-1] + 1;
	
	for(int i = 1;i < LOG;i++)up[n][i] = up[up[n][i-1]][i-1];
	

}

void UndoCommands(int x) {
	++n;
	up[n][0] = n - x - 1;
	dep[n] = dep[n - x - 1];
	for(int i = 1;i < LOG;i++)up[n][i] = up[up[n][i-1]][i-1];
	
}

char GetLetter(int x) {
	++x;
	int u = n;
	for(int i = LOG - 1;i >= 0;i--){
		if(dep[up[u][i]] >= x){
			u = up[u][i];
		}
	}
	return A[u];
}

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