Submission #94056

#	Time	Username	Problem	Language	Result	Execution time	Memory
94056		fjzzq2002	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	457 ms	142420 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define SZ 20005555
int an=0,ch[SZ][2];
char va[SZ];
int edt(int x,int l,int r,int p,char u)
{
	int y=++an;
	if(l==r) {va[y]=u; return y;}
	int m=(l+r)>>1;
	if(p<=m)
		ch[y][1]=ch[x][1],
		ch[y][0]=edt(ch[x][0],l,m,p,u);
	else
		ch[y][0]=ch[x][0],
		ch[y][1]=edt(ch[x][1],m+1,r,p,u);
	return y;
}
char qry(int x,int l,int r,int p)
{
	if(l==r) return va[x];
	int m=(l+r)>>1;
	if(p<=m) return qry(ch[x][0],l,m,p);
	return qry(ch[x][1],m+1,r,p);
}
int rs[SZ],cu=0,ls[SZ];
void Init() {}
void TypeLetter(char L)
{
	++cu; ls[cu]=ls[cu-1]+1;
	rs[cu]=edt(rs[cu-1],0,1.001e6,ls[cu-1],L);
}
void UndoCommands(int U)
{
	++cu; ls[cu]=ls[cu-U-1]; rs[cu]=rs[cu-U-1];
}
char GetLetter(int P)
{return qry(rs[cu],0,1.001e6,P);}

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