Submission #96314

#	Time	Username	Problem	Language	Result	Execution time	Memory
96314		figter001	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	671 ms	97912 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6+50;

char last;

struct node{
	char c;
	int up[21],sz;
	node(){
		c = 0;
		sz = 0;
		memset(up,-1,sizeof(up));
	}
}v[maxn];
int cur;

void Init(){}

void TypeLetter(char L) {
	cur++;
	v[cur].c = L;
	v[cur].up[0] = cur-1;
	v[cur].sz = v[cur-1].sz + 1;
	int tmp = cur-1;
	for(int i=1;i<20;i++){
		if(tmp == -1)break;
		v[cur].up[i] = v[tmp].up[i-1];
		tmp = v[tmp].up[i-1];
	}
}

void UndoCommands(int U) {
	cur++;
	v[cur] = v[cur-U-1];
}

char GetLetter(int P) {
	int m = v[cur].sz - P - 1;
	int tmp = cur;
	for(int i=20;i>=0;i--){
		if((m>>i) & 1)tmp = v[tmp].up[i];
	}
  	return v[tmp].c;
}

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