Submission #791072

#	Time	Username	Problem	Language	Result	Execution time	Memory
791072		jlallas384	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	340 ms	142136 KiB

scrivener

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

const int N = 1000001;
int lc[N * 27], rc[N * 27];
char st[N * 27];
int sz[N], rt[N], cur = 1;
int idx = 0;
int upd(int p, int l, int r, int i, char x){
	int nd = cur++;
	if(l == r){
		st[nd] = x;
	}else{
		int m = (l + r) / 2;
		lc[nd] = lc[p], rc[nd] = rc[p];
		if(i <= m) lc[nd] = upd(lc[nd], l, m, i, x);
		else rc[nd] = upd(rc[nd], m + 1, r, i, x);
	}
	return nd;
}

char qry(int p, int l, int r, int i){
	if(l == r){
		return st[p];
	}else{
		int m = (l + r) / 2;
		if(i <= m) return qry(lc[p], l, m, i);
		else return qry(rc[p], m + 1, r, i);
	}
}

void Init(){

}

void TypeLetter(char L){
	rt[idx + 1] = upd(rt[idx], 0, 1000000, sz[idx], L);
	sz[idx + 1] = sz[idx] + 1;
	idx++;
}

void UndoCommands(int U){
	rt[idx + 1] = rt[idx - U];
	sz[idx + 1] = sz[idx - U];
	idx++;
}

char GetLetter(int P){
	return qry(rt[idx], 0, 1000000, P);
}

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