Submission #576060

#	Time	Username	Problem	Language	Result	Execution time	Memory
576060		benson1029	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	458 ms	90572 KiB

scrivener

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

char curr[1000005];
int sparse[1000005][21];
int cntop;
int len[1000005];

void Init() {
	cntop = 0;
}

void TypeLetter(char L) {
	cntop++;
	len[cntop] = len[cntop-1] + 1;
	curr[cntop] = L;
	sparse[cntop][0] = cntop-1;
	for(int i=1; i<=20; i++) {
		if(sparse[cntop][i-1] == 0) sparse[cntop][i-1] = 0;
		else sparse[cntop][i] = sparse[sparse[cntop][i-1]][i-1];
	}
}

void UndoCommands(int U) {
	cntop++;
	len[cntop] = len[cntop-U-1];
	curr[cntop] = curr[cntop-U-1];
	for(int i=0; i<=20; i++) sparse[cntop][i] = sparse[cntop-U-1][i];
}

char GetLetter(int P) {
	P++;
	int ptr = len[cntop], tmp = cntop;
	for(int i=20; i>=0; i--) {
		if(ptr - (1<<i) >= P) {
			ptr -= (1<<i);
			tmp = sparse[tmp][i];
		}
	}
	return curr[tmp];
}

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