Submission #752057

#	Time	Username	Problem	Language	Result	Execution time	Memory
752057		LCJLY	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	449 ms	87408 KiB

scrivener

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

int par[1000005][20];
int arr[1000005];
char ans[1000005];
int d[1000005];
int ptr=0;

void Init() {
	//binary lifting
	memset(par,-1,sizeof(par));
}

void TypeLetter(char L) {
	ptr++;
	arr[ptr]=ptr;
	ans[ptr]=L;
	par[ptr][0]=arr[ptr-1];
	d[ptr]=d[arr[ptr-1]]+1;
	
	//binary lifting
	for(int x=1;x<20;x++){
		if(par[ptr][x-1]==-1) continue;
		par[ptr][x]=par[par[ptr][x-1]][x-1];
	}
}

void UndoCommands(int U) {
	ptr++;
	arr[ptr]=arr[ptr-U-1];
}

char GetLetter(int P) {
	//binary lifting
	int diff=d[arr[ptr]]-P-1;
	int target=arr[ptr];
	
	for(int x=0;x<20;x++){
		if(diff&(1<<x)){
			target=par[target][x];
		}
	}
	
	return ans[target];
}

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