Submission #335672

#	Time	Username	Problem	Language	Result	Execution time	Memory
335672		LucaDantas	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	611 ms	101228 KiB

scrivener

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

constexpr int maxn = 1e6+10, logn = 20;

int path[maxn][logn+1], last[maxn], pos;
int let[maxn], qtd[maxn], tam[maxn];

void Init() {}

void TypeLetter(char L) {
	++pos;
	qtd[pos] = qtd[last[pos-1]] + 1;
	tam[pos] = tam[last[pos-1]] + 1;
	last[pos] = pos;
	let[pos] = L-'a';
	path[pos][0] = last[pos-1];
	for(int l = 1, p = last[pos-1]; l <= logn; l++) {
		path[pos][l] = path[p][l-1];
		p = path[p][l-1];
	}
}

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

char GetLetter(int P) {
	int p = last[pos];
	P = tam[p] - P - 1;
	for(int l = logn; l >= 0; l--)
		if(P >= (1 << l)) p = path[p][l], P -= 1<<l;
	return char(let[p]+'a');
}

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