Submission #416036

#	Time	Username	Problem	Language	Result	Execution time	Memory
416036		arayi	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	877 ms	77124 KiB

scrivener

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define ad push_back
using namespace std;
const int N = 1e6 + 1;

int a[N], i1 = 1, nax[N];
int p[N][18];
char c[N];
void Init()
{

}

void TypeLetter(char L)
{
	a[i1] = a[i1 - 1] + 1;
	nax[i1] = nax[i1 - 1];
	c[i1++] = L;
}

void UndoCommands(int U)
{
	a[i1] = a[i1 - U - 1];
	nax[i1] = i1;
	p[i1][0] = nax[i1 - U - 1];
	for (int i = 1; i < 18; i++) p[i1][i] = p[p[i1][i - 1]][i - 1];
	i1++;
}

char GetLetter(int P)
{
	P++;
	int s = nax[i1 - 1];
	if (a[s] < P) return c[s + P - a[s]];
	for (int i = 17; i >= 0; i--) if (a[p[s][i]] >= P)s = p[s][i];
	s = p[s][0];
	return c[s + P - a[s]];
}

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