Submission #256677

#	Time	Username	Problem	Language	Result	Execution time	Memory
256677		tinjyu	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	537 ms	142200 KiB

scrivener

#include <iostream>
using namespace std;
char last;
int vis[1000005][2],loc,l[30000005],r[30000005],cnt,v;
char val,tree[30000005];
void Init(){
	vis[0][0]=0;
	vis[0][1]=0;
}
void clone(int a,int b)
{
	l[b]=l[a];
	r[b]=r[a];
	tree[b]=tree[a];
	return ;
}
int change(int node,int s,int e)
{
	//cout<<s<<" "<<e<<endl;
	cnt++;
	clone(node,cnt);
	if(s==e)
	{
		tree[cnt]=val;
		return cnt;
	}
	long long int now=cnt;
	if(vis[v][1]<=(s+e)/2)
	{
		l[now]=change(l[now],s,(s+e)/2);
	}
	else r[now]=change(r[now],(s+e)/2+1,e);
	return now;
}
char find(int node,int s,int e){
	if(s==e)return tree[node];
	if(loc<=(s+e)/2)return find(l[node],s,(s+e)/2);
	else return find(r[node],(s+e)/2+1,e);
}
void TypeLetter(char L) {
	v++;
	val=L;
	vis[v][0]=cnt+1;
	vis[v][1]=vis[v-1][1]+1;
	change(vis[v-1][0],1,1000000);
}
void UndoCommands(int U) {
	v++;
	vis[v][0]=vis[v-U-1][0];
	vis[v][1]=vis[v-U-1][1];
	return ;
}
 
char GetLetter(int P) {
	loc=P+1;
	return find(vis[v][0],1,1000000);
}

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